基本单链表和基本顺序表

一、目的 1. 领会顺序表存储结构和掌握顺序表中各种基本运算算法设计； 2. 领会单链表存储结构和掌握单链表中各种基本运算算法设计。

二、内容 1.编写一个程序sqlist.c,实现顺序表的各种基本运算和整体建表算法（假设顺序表的元素类型ElemType为char），并在此基础上设计一个主程序，完成如下功能： （1）初始化顺序表L （2）依次插入a,b,c,d,e元素 （3）输出顺序表L （4）顺序表L长度 （5）判断顺序表L是否为空 （6）输出顺序表L的第3个元素 （7）输出元素a的位置 （8）在第4个元素位置上插入f元素 （9）输出顺序表L （10）删除L的第3个元素 （11）输出顺序表L （12）释放顺序表L 2.编写一个程序linklist.c,实现单链表的各种基本运算和整体建表算法（假设单链表的元素类型ElemType为char），并在此基础上设计一个主程序，完成如下功能： （1）初始化单链表L （2）依次插入a,b,c,d,e元素 （3）输出单链表L （4）单链表L长度 （5）判断单链表L是否为空 （6）输出单链表L的第3个元素 （7）输出元素a的位置 （8）在第4个元素位置上插入f元素 （9）输出单链表L （10）删除L的第3个元素 （11）输出单链表L （12）释放单链表L

三、源代码 1.基本顺序表

#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define MaxSize 50 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; void CreatList(SqList **L, ElemType a[], int n) { *L = (SqList*)malloc(sizeof(SqList)); for (int i = 0; i < n; i++) (*L)->data[i] = a[i]; (*L)->length = n; } void InitList(SqList **L) { *L = (SqList*)malloc(sizeof(SqList)); (*L)->length = 0; } void DestroyList(SqList* *L) { free(*L); } int ListEmpty(SqList* L) { return(L->length == 0); } int ListLength(SqList* L) { return(L->length); } void DispList(SqList* L) { for (int i = 0; i < L->length; i++) { printf("%c", L->data[i]); } printf("\n"); } int GetElem(SqList* L, int i, ElemType *e) { if (i<1 || i>L->length) return 0; *e = L->data[i - 1]; return 1; } int LocateElem(SqList* L, ElemType e) { int i = 0; while (i < L->length&&L->data[i] != e) i++; if (i >= L->length) return 0; else return i + 1; } int ListInsert(SqList* *L, int i, ElemType e) { int j; if (i<1 || i>(*L)->length + 1) return 0; i--; for (j = (*L)->length; j > i; j--) (*L)->data[j] = (*L)->data[j - 1]; (*L)->data[i] = e; (*L)->length++; return 1; } int ListDelete(SqList* *L, int i, ElemType *e) { int j; if (i<1 || i>(*L)->length) return 0; i--; *e = (*L)->data[i]; for (j = i; j < (*L)->length - 1; j++) (*L)->data[j] = (*L)->data[j + 1]; (*L)->length--; return 1; } int main() { SqList *L; ElemType e; printf("顺序表的基本运算如下：\n"); printf("（1）初始化顺序表L\n"); InitList(&L); 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："); DispList(L); printf("（4）顺序表L长度：%d\n", ListLength(L)); printf("（5）顺序表L为%s\n", (ListEmpty(L) ? "空" : "非空")); GetElem(L, 3, &e); printf("（6）顺序表L的第3个元素：%c\n", e); printf("（7）元素a的位置：%d\n", LocateElem(L, 'a')); printf("（8）在第4个元素位置上插入f元素\n"); ListInsert(&L, 4, 'f'); printf("（9）输出顺序表L："); DispList(L); printf("（10）删除L的第3个元素\n"); ListDelete(&L, 3, &e); printf("（11）输出顺序表L："); DispList(L); printf("（12）释放顺序表L\n"); DestroyList(&L); system("pause"); return 1; }

2.基本单链表

#include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef char ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LinkNode; void CreateListF(LinkNode **L, ElemType a[], int n) { LinkNode *s; (*L) = (LinkNode *)malloc(sizeof(LinkNode)); (*L)->next = NULL; for (int i = 0; i < n; i++) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = a[i]; s->next = (*L)->next; (*L)->next = s; } } 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; } void DestroyList(LinkNode **L) { LinkNode *pre = *L, *p = (*L)->next; while (p != NULL) { free(pre); pre = p; p = p->next; } free(p); } int ListEmpty(LinkNode *L) { return(L->next == NULL); } int ListLength(LinkNode *L) { int i = 0; LinkNode *p = L; while (p->next != NULL) { i++; p = p->next; } return(i); } void DispList(LinkNode *L) { LinkNode *p = L->next; while (p != NULL) { printf("%c ", p->data); p = p->next; } printf("\n"); } int GetElem(LinkNode *L, int i, ElemType *e) { int j = 0; LinkNode *p = L; if (i <= 0)return 0; while (j < i&&p != NULL) { j++; p = p->next; } if (p == NULL) return 0; else { *e = p->data; return 1; } } int LocateElem(LinkNode *L, ElemType e) { int i = 1; LinkNode *p = L->next; while (p != NULL && p->data != e) { i++; p = p->next; } if (p == NULL) return 0; else return i; } int ListInsert(LinkNode **L, int i, ElemType e) { LinkNode *p = *L, *s; int j = 0; if (i <= 0)return 0; while (j < i - 1 && p != NULL) { j++; p = p->next; } if (p == NULL) return 0; else { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = e; s->next = p->next; p->next = s; return 1; } } int ListDelete(LinkNode **L, int i, ElemType *e) { LinkNode *p = *L, *q; int j = 0; if (i <= 0)return 0; while (j < i - 1 && p != NULL) { j++; p = p->next; } if (p == NULL) return 0; else { q = p->next; if (q == NULL) return 0; *e = p->next->data; p->next = q->next; free(q); return 1; } } int main() { LinkNode *h; ElemType e; printf("单链表的基本运算如下：\n"); printf(" (1)初始化单链表h\n"); InitList(&h); printf(" (2)依次插入a、b、c、d、e元素\n"); ListInsert(&h, 1, 'a'); ListInsert(&h, 2, 'b'); ListInsert(&h, 3, 'c'); ListInsert(&h, 4, 'd'); ListInsert(&h, 5, 'e'); printf(" (3)输出单链表h:"); DispList(h); printf(" (4)单链表h长度：%d\n", ListLength(h)); printf(" (5)单链表h为%s\n", (ListEmpty(h) ? "空" : "非空")); GetElem(h, 3, &e); printf(" (6)单链表h的第3个元素:%c\n", e); printf(" (7)元素a的位置:%d\n", LocateElem(h, 'a')); printf(" (8)在第4个元素位置上插入f元素\n"); ListInsert(&h, 4, 'f'); printf(" (9)输出单链表h："); DispList(h); printf(" (10)删除h的第3个元素\n"); ListDelete(&h, 3, &e); printf(" (11)出单链表h："); DispList(h); printf(" (12)释放单链表h\n"); DestroyList(&h); system("pause"); return 0; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！