🔥码云GVP开源项目 12k star Uniapp+ElementUI 功能强大 支持多语言、二开方便! 广告
# 线性表 ## 概念 线性表是具有相同特性的数据元素的一个有限序列。 ### 逻辑特征 线性表中的元素位置是有序的,这种位置关系构成了一种线性关系,因此线性表是一个线性结构,即对于至少含有一个数据元素的线性表,除起始元素外均有且仅有一个前驱,除终端元素外均有且仅有一个后继。若线性表中的元素按照某种顺序排列,则称该线性表为有序表。 ### 存储结构 有顺序和链式两种存储结构,分别称为顺序表和链表。链表的每个节点包含数据域和指针域,第一个节点的存储位置称为头指针,如果链表带有头结点,那头指针为头结点的地址,否者为起始节点。 ## 顺序表 定义 ```c #define MaxSize 50 typedef struct { ElemType data[MaxSize]; int length; }SqList; ``` 初始化顺序表 ```C void InitList(SqList &L) { L.length = 0; } ``` 求指定位置元素 ```C int GetElem(SqList L, int i, ElemType &e) { if(i < 1 || i > L.length) return 0; e = L.data[i-1]; return 1; } ``` 按元素查找 ```C int LocateElem(SqList L, int &n, ElemType e) { if(L == NULL) return 0; int i = 0; while(L.data[i] != e && i < L.length) i++; if(i == L.length) return 0; n = i+1; return 1; } ``` 插入数据元素(插到第 i 个位置上) ```C int ListInsert(SqList &L, ElemType e, int i) { if(i < 1 || i > L.length+1) return 0; L.length++; int j; for(j = L.length-1; j >= i; j--) L.data[j] = L.data[j-1]; L.data[j] = e; return 1; } ``` 删除数据元素 ```C int ListDelete(SqList &L, int i, ElemType &e) { if(i < 1 || i > L.length) return 0; e = L.data[i-1]; for(int j = i-1; j < L.length-1; j++) L.data[j] = L.data[j+1]; L.lenght--; return 1; } ``` 有序顺序表的归并算法 ```C void MergeList(SqList L1, SqList L2, SqList &L3) { int i = 0, j = 0, k = 0; while(i < L1.length && j < L2.length){ if(L1.data[i] < L2.data[j]){ L3.data[k] = L1.data[i]; k++; i++; }else if(L1.data[i] > L2.data[j]){ L3.data[k] = L2.data[j]; k++; j++; }else{ L3.data[k] = L1.data[i]; k++; i++; j++; } } while(i < L1.length){ L3.data[k] = L1.data[i]; k++; i++; } while(j < L2.length){ L3.data[k] = L1.data[j]; k++; j++; } L3.length = k; } ``` ## 单链表 定义 ```C typedef struct LNode{ ElemType data; LNode *next; }LinkList; ``` 头插法建立单链表(次序与原来次序相反) ```C void CreateListF(LinkList *&L, ElemType a[], int n) { LinkList *s; int i; L = (LinkList *)malloc(sizeof(LinkList)); //创建头结点 L->next = NULL; for(i = 0, i < n, i++){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = a[i]; s->next = L->next; L->next= s; } } ``` 尾插法建立单链表(次序与原来次序相同) ```C void CreateListR(LinkList *&L, ElemType a[], int n) { LinkList *s, *r; int i; L = (LInkList *)malloc(sizeof(LinkList)); L->next = NULL; r = L; for(i=0, i<n, i++){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = a[i]; r->next = s; r = s; } r->next = NULL; } ``` 按元素查找 ```C int LocateElem(LinkList *L, ElemType e) { LinkList *p = L->next; int i = 1; while(p!=NULL && p->data!=e){ p = p->next; i++; } if(p==NULL) return 0; else return i; } ``` 将 e 插入到单链表的第 i 个节点位置上 ```C int InsertElem(LinkList *&L, ElemType e, int n) { LinkList *p = L, *s; // p 为第一个节点位置的前一个节点 int j = 0; while(p!=NULL && j<n-1){ p = p->next; j++; } if(p!=NULL){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = e; s->next = p->next; p->next = s; return 1; } else return 0; } ``` 删除第 i 个节点位置上的元素 ```C int DeleteElem(LinkList *&L, ElemType &e, int n) { LinkList *p = L, *q; // p 为第一个节点位置的前一个节点 int j = 0; while(p!=NULL && j<n-1){ p = p->next; j++; } if(p!=NULL && p->next!=NULL){ q = p->next; p->next = q->next; free(q); return 1; } else return 0; } ``` 有序单链表的归并(新建单链表) ```C void MergeList1(LinkList *L1, LinkList *L2, LinkList *&L3) { LinkList *s1 = L1->next, *s2 = L2->next, *r, *s; L3 = (LinkList *)malloc(sizeof(LinkList)); L3->next = NULL; r = L3; while(s1!=NULL && s2!=NULL){ if(s1->data < s2->data){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = s1->data; r->next = s; r = s; s1 = s1->next; }else if(s1->data > s2->data){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = s2->data; r->next = s; s2 = s2->next; r = s; }else{ s = (LinkList *)malloc(sizeof(LinkList)); s->data = s1->data; r->next = s; r = s; s1 = s1->next; s2 = s2->next; } } if(s2!=NULL) s1 = s2; while(s1!=NULL){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = s1->data; r->next = s; r = s; s1 = s1->next; } r->next = NULL; } ``` 有序单链表的归并(要求空间复杂度为 O(1) ,即舍弃原来的两个单链表) ```C void MergeList(LinkList *L1, LinkList *L2, LinkList *&L3) { LinkList *p = L1->next, *q = L2->next; L3 = (LinkList *)malloc(sizeof(LinkList)); L3 = L1; free(L2); r = L3; while(p!=NULL && q!=NULL){ if(p->data < q->data){ r->next = p; p = p->next; } else if(p->data > q->data){ r->next = q; q = q->next; } else{ r->next = p; p = p->next; q = q->next; } } if(q!=NULL) p = q; r->next = p; } ``` ## 双链表 双链表头尾不相接 定义 ```C typedef struct DLinkList{ ElemType data; DLinkList *next; DLinkList *prior; }DLinkList; ``` 头插法建立双链表 ```C void CreateDListF(DLinkList *&L, ElemType a[], int n) { DLinkList *s; L = (DLinkList *)malloc(sizeof(DLinkList)); L->next = L->prior = NULL; for(int i=0; i<n; i++){ s = (DLinkList *)malloc(sizeof(DLinkList)); s->data = a[i]; s->next = L->next; if(L->next!=NULL) L->next->prior = s; L->next = s; s->prior = L; } } ``` 尾插法建立双链表 ```C void CreateDListR(DLinkList *&L, ElemTyoe a[], int n) { DLinkList *s, *r; L = (DLinkList *)malloc(sizeof(DLinkList)); L->next = L->prior = NULL; r = L; for(int i=0; i<n; i++){ s = (DLinkList *)malloc(sizeof(DLinkList)); s->data = a[i]; r->next = s; s->prior = r; r = s; } r->next = NULL; } ``` 查找指定元素节点 ```C int FindNode(DLinkList *L, ElemType e) { DLinkList *p = L->next; int i = 1; while(p!=NULL && p->data != e){ p = p->next; i++; } if(p!=NULL) return i; else return 0; } ``` 将 e 插入第 n 个节点位置 ```C int InsertNode(DLinkList *&L, ElemType e, int n) { DLinkList *p, *s; int i = 0; p = L; while(p!=NULL && i<n-1){ p = p->next; i++; } if(p!=NULL){ s = (DLinkList *)malloc(sizeof(DLinkList)); s->data = e; s->next = p->next; s->prior = p; if(p->next!=NULL){ p->next->prior = s; p->next = s; } return 1; } else return 0; } ``` 删除第 n 个节点位置的元素 ```C int DeleteNode(DLinkList *&L, ElemType e, int n) { DLinkList *p, *q; int i = 0; p = L; while(p!=NULL && i<n-1){ p = p->next; i++; } if(p!=NULL){ q=p->next; if q==NULL; return 0; p->next = q->next; if(q->next!=NULL) q->next->prior = p; free(q); return 1; } else return 0; } ``` ## 循环链表 定义 ```C typedef struct LNode{ ElemType data; next LNode *next; }LinkList; ``` 头插法建立循环链表 ```C void CreateListF(LinkList *&L, ElemType a[], int n) { LinkList *s; int i; L = (LinkList *)malloc(sizeof(LinkList)); L->next = L; for(i=0; i<n; i++){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = a[i]; s->next = L->next; L->next = s; } } ``` 尾插法建立循环链表 ```C void CreateListR(LinkList *&L, ElemType a[], int n) { LinkList *s, *r; int i; L = (LinkList *)malloc(sizeof(LinkList)); L->next = L; r = L; for(i=0; i<n; i++){ s = (LinkList *)malloc(sizeof(LinkList)); s->data = a[i]; r->next = s; r = s; } r->next = L; } ``` 查找元素值为 e 的节点 ```C int FindNode(LinkList *L, ElemTpye e) { LinkList *p = L->next; int i = 1; while(p!=L && p->data = e){ p = p->next; i++; } if(p==L) return 0; else return i; } ``` ## 静态链表 ```C++ struct Node{ typename data; // 数据域 int next; // 存放下一个结点的数组下标 xxx; // 结点的某些性质 } ``` ## 申请动态内存函数 ### C 语言 malloc 函数:`typename* p=(typename*)malloc(sizeof(typename));` 对应的内存释放函数 free :`free(p);` ### C++ new 函数:`typename* p=new typename;` 对应的内存释放函数 delete :`delete(p);`