本文共 7754 字，大约阅读时间需要 25 分钟。
一、线性表定义:
线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，其中的结点，有且仅有一个开始结点(第一元素)没有前驱但有一个后继结点，有且仅有一个终端结点（最后节点）没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。
上述定义可以用下列图像记忆
如一对有序序列(A,B,C,............Z)
图表示为
（^，A(第一节点，没有前驱但有一个后继结点),B,C ……(其它的结点都有且仅有一个前驱和一个后继结点)……….Z（最后节点,没有后继但有一个前驱结点），^）
总结：凡是符合上图特点的均可以认为是线性表。
二、线性表的顺序表示与链式表示的区别
顺序表
存储图如下
特点:
一、逻辑上相邻的数据元素，物理存储位置也相邻。（逻物一致）
二、顺序表的存储空间需要预先分配。
优点：
（1）方法简单，各种高级语言中都有数组，容易实现。（语言通用性）
（2）不用为表示节点间的逻辑关系而增加额外的存储开销。(内存节约性)
（3）顺序表具有按元素序号随机访问的特点。(逻物一致性)
缺点：
（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。（操作低效率）
（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。（内存固定性）
链式表
存储图如下
特点：
一、逻辑上相邻的数据元素，物理存储位置不一定相邻。（逻物不一定一致）
二、它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。
链表的最大特点是：插入、删除运算方便。（插入、删除方便）
优点：
(1)插入、删除运算方便。（插入、删除方便）
(2)内存空间动态分配使得内存使用率高，内存不易溢出。(内存动态分配性)
缺点：
（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。(内存浪费或内存有效使用率低)
（2）链表不是一种随机存储结构，不能随机存取元素。（逻物不一致）
总结： 顺序表是一种牺牲cpu为代价但节省内存的数据存储方式，链式表是以牺牲内存代价的高效率的存储方式。
实践应用中怎样选取存储结构呢？
1).内存使用率
一般以一顺序存储为主，
但线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。
2)基于运算的考虑（时间）
如果不对线性表频发插入或删除操作，以顺序表优先考虑；
否则以链式表优先考虑
三、 线性列表代码：
以顺序存储为例的代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | #include<stdio.h> #include<malloc.h> #include<stdlib.h> #define ERROR 0 #define OK 1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int Status; typedef int ElemType; typedef struct { int *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList &L) { L.elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof (ElemType)); if (!L.elem) exit (OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; } //插入 Status ListInsert_Sq(SqList &L, int i, ElemType e) { ElemType *newbase, *q, *p; if (i < 1 || i > L.length + 1) return ERROR; if (L.length >= L.listsize) { newbase = (ElemType *) realloc (L.elem, (L.listsize + LISTINCREMENT) * sizeof (ElemType)); if (!newbase) exit (OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT; } q = &(L.elem[i - 1]); for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p+1) = *p; *q = e; ++L.length; return OK; } //创建 Status CreateList_Sq(SqList &L, int n){ int i; ElemType e; printf ( "Please input %d elements:\n" , n); for (i = 1; i <= n; i++){ scanf ( "%d" ,&e); ListInsert_Sq(L, i, e); } return OK; } //删除 Status DeleteList_Sq(SqList &L, int i, ElemType *e){ ElemType *p, *q; if (i <= 0 || i > L.length) return ERROR; p = &L.elem[i-1]; *e = *p; q = L.elem + L.length ; for (++p; p < q; ++p) *(p - 1) = *p; --L.length; return OK; } //查找 Status LocateElem(SqList L, int num){ int i = 1; ElemType *p; p = L.elem; while (i <= L.length && *p != num ) { ++i; ++p; } if (i < L.length) return i; else return 0; } //排序 Status ListAscend_Sq(SqList &L){ int i, j, k; ElemType t; for (i = 0; i < L.length; i++) { k = i; for (j = i+1; j < L.length; j++) if (L.elem[j] < L.elem[k]) k = j; if (k != i) { t = L.elem[i]; L.elem[i] = L.elem[k]; L.elem[k] = t; } } return OK; } //输出 void Print_Sq(SqList L) { int i; for (i = 0; i < L.length; i++) printf ( "%d " ,L.elem[i]); printf ( "\n" ); } void main() { Status i, e, num, de, location, position, result; SqList MyList; InitList_Sq(MyList); //初始化 CreateList_Sq(MyList, 10); //创建 printf ( "\n" ); //插入 printf ( "Please input the number's position and the number to be inserted:" ); scanf ( "%d,%d" , &i, &e); ListInsert_Sq(MyList,i, e); printf ( "\n" ); printf ( "Inserted list:\n" ); Print_Sq(MyList); printf ( "\n" ); //删除 printf ( "Please input the position(to be deleted):" ); scanf ( "%d" , &position); result = DeleteList_Sq(MyList, position, &de); if (result == OK) printf ( "The %dth element %d has been deleted.\n" , position, de); Print_Sq(MyList); //查找 printf ( "\n" ); printf ( "Please input the located number:" ); scanf ( "%d" ,&num); location = LocateElem(MyList, num); if (location < 1) printf ( "DO NOT EXIST!" ); else printf ( "Location:%d" ,location); printf ( "\n\n" ); ListAscend_Sq(MyList); //排序 // printf("\n\n"); printf ( "The sorted list by ascending:\n" ); Print_Sq(MyList); //输出 printf ( "\n" ); free (MyList.elem); //释放空间 } |
以链式存储为例的代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int ElemType; typedef struct LNode { //定义类型链式节点 ElemType data; struct LNode * next; }LNode, *LinkList; Status InitList_L(LinkList &L){ //初始化链表L，链表的节点个数初始化data = 0； next = null L = (LinkList) malloc ( sizeof (LNode)); //分配内存空间 if (!L) return ERROR; L->data = 0; //节点个数,或称为表长（表的长度） L->next = NULL; return OK; } Status Insert_L(LinkList &L, int i, ElemType e){ //向链表插入元素e LNode *p, *q; int j = 0; p = L; while (p && j < i - 1){ p = p->next; ++j; } if (!p || j > i - 1) return ERROR; q = (LinkList) malloc ( sizeof (LNode)); q->data = e; //insert element q->next = p->next; p->next = q; L->data++; //每插入也节点，表长自加1 return OK; } Status Delete_L(LinkList &L, int i, ElemType e){ //删除节点e LNode *p, *q; p = L; int j = 0; while (p->next && j < i - 1){ p = p->next; ++j; } if (!(p->next) || j > i - 1) return ERROR; q = p->next; p->next = q->next; e = q->data; free (q); L->data--; //每删除一个节点，表长自减1 return OK; } Status GetElem_L(LinkList L, int i, ElemType &e){ //获取第i个元素，赋值于e LNode *p; int j = 1; p = L->next; while (p && j < i){ p = p->next; ++j; } if (!p || j > i) return ERROR; e = p->data; return OK; } Status Create_L(LinkList &L){ //创建链表，赋值元素 ElemType temp; printf ( "Please input data<9999>ending\n" ); scanf ( "%d" , &temp); while (temp != 9999){ Insert_L(L, L->data+1, temp); scanf ( "%d" , &temp); } return OK; } Status Traverse_L(LinkList L){ //遍历线性表 LNode *p = L->next; printf ( "List contains %d elements:\n" ,L->data); while (p){ printf ( "%5d-->" ,p->data); p = p->next; } printf ( "NULL\n" ); return OK; } Status DeleteBet(LinkList &L, ElemType mink, ElemType maxk){ //删除值在(mink,maxk)之间的值 LinkList p, q; p = L; if ((mink >= maxk) ||(p->next == NULL)) exit (ERROR); while (p){ if (p->next->data > mink){ while (p->next->data < maxk){ q = p->next; p->next = p->next->next; free (q); L->data --; } break ; } p = p->next; } return OK; } void main(){ LinkList L; int i, i1, i2, e, e1, e2, j1, j2; InitList_L(L); //初始化链表 Create_L(L); //赋值链表 printf ( "The length is:%d\n" , L->data); Traverse_L(L); //遍历输出节点值 printf ( "GetElem i:" ); scanf ( "%d" , &i); GetElem_L(L, i, e); printf ( "The NO.%d element is:%d \n" , i, e); printf ( "InsertPosition:" ); scanf ( "%d" , &i1); printf ( "Insert element:" ); scanf ( "%d" , &e1); Insert_L(L, i1, e1); Traverse_L(L); //遍历输出节点值 printf ( "Delete position:" ); scanf ( "%d" , &i2); Delete_L(L, i2, e2); Traverse_L(L); //遍历输出节点值 printf ( "\nDelete between(a,b):" ); scanf ( "%d,%d" ,&j1, &j2); DeleteBet(L, j1, j2); printf ( "The result is:%d\n" ); Traverse_L(L); //遍历输出节点值 } |
四、知识点回顾
线性表的链式存储及特点
–逻物不一定一致、顺序存取、空间利用充分、插删方便
• 单链表(线性链表)及C语言实现
• 头指针、头结点、首元结点
• 单链表的建立、查找、插入、删除、输出
• 单链表与顺序表的比较，及挑
本文转自lilin9105 51CTO博客，原文链接：http://blog.51cto.com/7071976/1206925，如需转载请自行联系原作者