//以下为线性表的（带头节点的）链式存储结构的实现，请补充完整。#include #include typedef char ElemType;typedef struct Node /*结点类型定义*/{ ElemType data;//数据元素 struct Node *next;//下一个元素的指针}Node, *LinkList; /*LinkList为指向Node结构的指针类型，LinkList与Node *等价*/LinkList CreateList(void);//创建链表，返回指向头结点的指针void printList(LinkList L);//打印链表Lint isEmpty(LinkList L);//1:空表，0：非空void destroyList(LinkList L);//清空链表（删除链表L的元素）int GetLength(LinkList L);//计算链表的长度Node* Get(LinkList L, int i);//返回L的 指向第i个元素的指针，i>=0,i<=表的长度；//如果i不在该范围，返回NULLNode *Locate(LinkList L, ElemType key);//在线性表L中找元素key,找到，返回指向该元素的指针，否则返回NULLint InsList(LinkList L, int i, ElemType e);//向L中插入元素e,作为L的第i个元素.1<=i<=Length+1int DelList(LinkList L, int i, ElemType *e);LinkList MergeLinkList(LinkList LA, LinkList LB);/*将递增有序表LA和LB合并为有序表LC*/int main(){ LinkList L; printf("输入L的数据(字符)，以$结束:\n"); L = CreateList(); printList(L); int len; len = GetLength(L); printf("length=%d\n", len); Node *s; s = Get(L, 1); if (s) {printf("Get(L, 1)=%c\n", s->data); } else {printf("Get(L, 1)=没有该元素\n"); } s = Get(L, 3); if (s) {printf("Get(L, 3)=%c\n", s->data); } else {printf("Get(L, 3)=没有该元素\n"); } s = Get(L, 4); if (s) {printf("Get(L, 4)=%c\n", s->data); } else {printf("Get(L, 4)=没有该元素\n"); } s = Locate(L, 'A'); if (s) {printf("Locate(L, 'A')=%c\n", s->data); } else {printf("Locate(L, 'A')=没有该元素\n"); } s = Locate(L, 'D'); if (s) {printf("Locate(L, 'D')=%c\n", s->data); } else {printf("Locate(L, 'D')=没有该元素\n"); } int r; r = InsList(L, 1, 'D'); if (r == 0) printf("插入失败\n"); printList(L); r = InsList(L, GetLength(L) + 1, 'F'); if (r == 0) printf("插入失败\n"); printList(L); ElemType c; r = DelList(L, 1, &c); if (r) {printf("c=%c\n", c); } printList(L); DelList(L, GetLength(L), &c); printList(L); r = DelList(L, 100, &c); if (r == 0) printf("失败\n"); getchar();//将输入缓冲区中的回车键读取（取走） LinkList L1, L2, L3; printf("输入L1的数据(字符)，以$结束:\n"); L1 = CreateList(); printf("L1=\n"); printList(L1); getchar();//将输入缓冲区中的回车键读取（取走） printf("输入L2的数据(字符)，以$结束:\n"); L2 = CreateList(); printf("L2=\n"); printList(L2); printf("L2的长度（元素个数）=%d\n", GetLength(L2)); L3 = MergeLinkList(L1, L2); printf("L1=\n"); printList(L1); printf("L2=\n"); printList(L2); printf("L3=\n"); printList(L3); return 0;}LinkList MergeLinkList(LinkList LA, LinkList LB){/*将递增有序表LA和LB合并为有序表LC*/ Node *pa, *pb, *s, *last; LinkList LC; LC = new Node; LC->next = (1) ; last = LC; pa = LA->next; pb = LB->next; while (pa != NULL && pb != NULL) {if (pa->data <= pb->data) {s = new Node;s->data = pa->data;pa = (2) ;s->next = NULL;// last->next;last->next = s;last = last->next;}else{s = new Node;s->data = pb->data;pb = pb->next;s->next = NULL;// last->next;last->next = s;last = last->next;} } while (pa) {s = new Node;s->data = pa->data;pa = pa->next;s->next = NULL;// last->next;last->next = s;last = last->next; } while (pb) {s = new Node;s->data = pb->data;pb = pb->next;s->next = NULL;// last->next;last->next = s;last = last->next; } return LC;}int DelList(LinkList L, int i, ElemType *e){ int len = GetLength(L); if (i<1 || i>len) return 0;//非法位置 Node *pre; pre = Get(L, i - 1); if (!pre) return 0;//其它bug Node *s; s = pre->next; *e = s->data; (3) ; delete s; return 1;}int InsList(LinkList L, int i, ElemType e){ int len = GetLength(L); if (i<1 || i>len + 1) return 0;//非法位置 Node *pre; pre = (4) ; if (!pre) return 0;//其它bug Node *s; s = new Node; if (!s) return 0;//存储空间满 s->data = e; s->next = pre->next; (5) ; return 1;}Node* Get(LinkList L, int i) { if (i<0 || i>GetLength(L)) return NULL; int c = 0; Node *s; s = L; if (c == i) return s; while (s->next) {c++; (6) ;if (c == i) return s; } return NULL;}Node *Locate(LinkList L, ElemType key) { Node *s; s = L->next; while ( (7) ) {if (s->data == key) return s;s = s->next; } return NULL;}LinkList CreateList(void) {//创建链表，返回指向头结点的指针LinkList L; Node *s; char c; //L= (LinkList)malloc(sizeof(Node)); L = new Node;//头结点，new 为C++运算符，申请一个Node结点（能存放Node结点的存储空间） L->next = NULL; c = getchar(); while (c != '$')//$为结束标志，不会加入到链表中 {s = new Node;s->data = c;s->next = L->next;L->next = s;c = getchar(); } return L;}void printList(LinkList L){ Node *s; s = (8) ; while (s) {printf("%c,", s->data);s = s->next; } printf("\n");}int GetLength(LinkList L){ Node *s; int c = 0; s = L->next; while (s) {c++;s = s->next; } return c;}int isEmpty(LinkList L)//1:空表，0：非空，//参数L:带头结点的链表的 头指针{ if (L->next == NULL) return 1; return 0;}void destroyList(LinkList L) { Node *s = L; Node *p; while (s->next) {p = s;s = s->next;delete p; } delete s;}