数据结构 C语言实现单链表的各种基本操作

编程入门行业动态更新时间:2024-10-11 09:26:28

数据结构 C语言实现单链表的各种基本操作

大概写了150多行，都是很基础的操作。需要的自取。
（书籍为数据结构教程（第五版）李春葆）

实验内容

实验三链表基本操作的实现

【实验目的】
1．掌握线性表的链式存储表示。
2．掌握单链表的基本操作，包括创建、查找、插入和删除等算法。
【实验内容】
编写程序linklist.cpp，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计主程序main.cpp，完成如下功能：
1．初始化单链表；
2．依次采用尾插法插入元素a，b，c，d，e；
3．输出单链表；
4．判断单链表的长度；
5．判断单链表是否为空；
6．输出单链表的第3个元素；
7．输出元素a的位置；
8．在第4个元素位置插入元素f；
9．输出单链表；
10．删除单链表的第3个元素；
11．输出单链表；
12．释放单链表。

#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode {		//定义单链表结点类型ElemType data;struct LNode *next;
} LinkNode;void CreateListR(LinkNode*&L,ElemType a[],int n) { //用尾插法创建单链表LinkNode *s,*r;L=(LinkNode*)malloc(sizeof(LinkNode));r=L;for(int i=0; i<n; i++) {s=(LinkNode*)malloc(sizeof(LinkNode));s->data=a[i];r->next=s;r=s;}r->next=NULL;
}
void InitList(LinkNode*&L) {       //初始化线性表L=(LinkNode*)malloc(sizeof(LinkNode));L->next=NULL;
}bool ListInsert(LinkNode*&L,int i,ElemType e) { //插入元素int j=0;LinkNode*p=L,*s;if(i<0) return false;while(j<i-1&&p!=NULL) {j++;p=p->next;}if(p==NULL)return false;else {s=(LinkNode*)malloc(sizeof(LinkNode));s->data=e;s->next=p->next;p->next=s;return true;}
}void DispList(LinkNode*L) { //输出单链表LinkNode*p=L->next;while(p!=NULL) {printf("%c",p->data);p=p->next;}
}int ListLength(LinkNode*L) { //输出单链表长度int n=0;LinkNode*p=L;while(p->next!=NULL) {n++;p=p->next;}return(n);
}bool ListEmpty(LinkNode*L) {//判断是否为空return (L->next==NULL);
}int LocateElem(LinkNode*L,ElemType e) {//按元素查找地址int i=1;LinkNode*p=L->next;while(p!=NULL&&p->data!=e) {p=p->next;i++;}if(p==NULL)return(0);else return(1);
}bool GetElem(LinkNode*L,int i,ElemType&e) { //查找元素int j;LinkNode*p=L;if(i<0) return false;while(j<i&&p!=NULL) {j++;p=p->next;}if(p==NULL)return false;else {e=p->data;return true;}
}bool ListDelete(LinkNode*&L,int i,ElemType&e) {int j=0;LinkNode*p=L,*q;if(i<=0)return false;while(j<i-1&&p!=NULL) {j++;p=p->next;}if(p==NULL)return false;else {q=p->next;if(p==NULL)return false;e=q->data;p->next=q->next;free(q);return true;}
}void DestoryList(LinkNode*&L) {LinkNode*pre=L,*p=L->next;while(p!=NULL) {free(pre);pre=p;p=pre->next;}free(pre);
}
int main() {LinkNode *L;ElemType e;InitList(L);printf("1.初始化单链表表\n");printf("2.依次插入元素a,b,c,d,e\n");ListInsert(L,1,'a');ListInsert(L,2,'b');ListInsert(L,3,'c');ListInsert(L,4,'d');ListInsert(L,5,'e');printf("3.输出单链表L：\n");DispList(L);printf("\n");printf("4.输出单链表长度:%d\n",ListLength(L));printf("5.单链表是否为空:",ListEmpty(L));printf("该单链表不为空\n");printf("6.第三个元素是:");GetElem(L,3,e);printf("%c\n",e);printf("7.元素a的位置是:%d\n",LocateElem(L,'a'));printf("8.在第4个元素位置插入元素f:\n");ListInsert(L,4,'f');DispList(L);printf("9.删除单链表的第3个元素:");ListDelete(L,3,e);DispList(L);printf("\n");printf("12．释放单链表\n");
}