顺序存储结构
用一段地址连续的存储单元存放存放线性表的数据元素
|
1 2 3 4 5 6 7 8 |
//结构 #define MAX_SIZE 20 typedef int ElemType; typedef struct { ElemType data[MAX_SIZE]; int length; }Sql_List; |
|
1 2 3 4 5 6 7 8 |
//获取元素 int GetElem(Sql_List L,int i,ElemType * e) { if(L.length == 0 || i < 1 || i > L.length) return 0; *e = L.data[i-1]; return 1; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//插入元素 int InsertElem(Sql_List * L,int i,ElemType e) { int k; if(L->length == MAX_SIZE) return 0; if(i < 1 || i > L->length+1) return 0; if(i <= L->length) { for(k = L->length-1;k >= i-1;k--) L->data[k+1] = L->data[k]; } L->data[i-1] = e; L->length++; return 1; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//删除元素 int DeleteElem(Sql_List * L,int i,ElemType * e) { int k; if(L->length == 0) return 0; if(i < 1 || i > L->length) return 0; *e = L->data[i-1]; if(i < L->length) { for(k = i;k < L->length;k--) L->data[k-1] = L->data[k] } L->length--; return 0; } |
链式存储结构
- 存储数据元素信息的域叫数据域
- 存储后继位置信息的域叫指针域
- 这两部分信息组成了结点，n个结点连接成了一个链表。每个结点只包含一个指针域，是单链表
- 链表中第一个结点的存储位置叫头指针。
- 一般会在单链表第一个结点前面设置一个结点，头结点
|
1 2 3 4 5 6 7 |
//结构 typedef struct Node { ElemType data; struct Node * next; } Node; typedef struct Node * LinkedList; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//单链表读取元素 int GetLinkElem(LinkedList L,int i,ElemType * e) { int j; LinkedList p; p = L->next; j = 1; while(p && j < i) { p = p->next; ++j; } if(!p || j > i) return 0; *e = p->data; return 1; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//单链表插入元素 int InsertLinkElem(LinkedList * L,int i,ElemType e) { int j; LinkedList p,s; p = *L; j = 1; while(p && j < i) { p = p->next; ++j; } if(!p || j > i) return 0; s = (LinkedList)malloc(sizeof(Node)); s->data = e; s->next = p->next->next; p->next = s; return 1; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//单链表删除元素 int DeleteLinkElem(LinkedList * L,int i,ElemType * e) { int j; LinkedList p,q; p = *L; j = 1; while(p && j < i) { p = p->next; ++j; } if(!(p->next) || j > i) return 0; q = p->next; p->next = q->next; *e = p->data; free(q); return 1; } |
|
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 |
//单链表整表创建-头插法 void CreateLinkedList(LinkedList * L,int n) { LinkedList p; int i; srand(time(0)); *L = (LinkedList)malloc(sizeof(Node));//头 (*L)->next = NULL; for(i = 0;i < n;++i) { p = (LinkedList)malloc(sizeof(Node)); p->data = rand() % 100 + 1; p->next = (*L)->next; (*L)->next = p;//头插法 } } //单链表整表创建-尾插法 void CreateLinkedList(LinkedList * L,int n) { LinkedList p,r; int i; *L = (LinkedList)malloc(sizeof(Node)); r = *L; for(i = 0;i < n;++i) { p = (LinkedList)malloc(sizeof(Node)); p->data = rand() % 100 + 1; r->next = p; r = p; } } //单链表整表删除 int ClearList(LinkedList *L) { LinkedList p,q; p = (*L)->next; while(p) { q = p->next; free(p); p = q; } (*L)->next = NULL; return 1; } |
静态链表
- 用数组描述的链表
|
1 2 3 4 5 6 |
#define MAXSIZE 1000 typedef struct { ElemType data; int cur; }StaticLinkList; |
初始化游标
|
1 2 3 4 5 6 7 8 |
Status InitList(StaticLinkList space) { int i; for (i = 0; i < MAXSIZE-1; i++) { space[i].cur = i+1; } space[MAXSIZE-1].cur = 0; return 0; } |
插入
|
1 2 3 4 5 6 7 8 9 10 11 |
int malloc_sll(StaticLinkList space) { // 数组第一个元素的游标值 // 返回第一个备用空间的下标 int i = space[0].cur; if (space[0].cur) { space[0].cur = space[i].cur; } return i; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Status ListInsert(StaticLinkList list, int i, ElemType e) { int j, k , l; k = MAX_SIZE - 1; if (i < 1 || i > ListLength(list)+1) { return ERROR; } // 获得空闲位置的下标 j = malloc_ssl(list); if (j) { list[j].data = e; for (l = 1; l <= i-1; l++) { k = list[k].cur; } list[j].cur = list[k].cur; list[k].cur = j; return OK: } return ERROR; } |
删除
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Status ListDelete(StaticLinkList list, int i) { int j, k; if (i < 1 || i > ListLength(list) - 1) { return ERROR; } k = MAXSIZE - 1; for (j = 1; j <= i - 1; j++) { k = list[k].cur; } j = list[k].cur; list[k].cur = list[j].cur; free_ssl(list, j); return OK; } void free+ssl(StaticLinkList space, int k) { space[k].cur = space[0].cur; space[0].cur = k; } |
长度
|
1 2 3 4 5 6 7 8 9 |
int ListLength(StaticLinkList list) { int j = 0; int i = list[MAXSIZE-1].cur; while(i) { i = list[i].cur; j++; } return j; } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 大话数据结构_赫夫曼树与应用01/11
- ♥ 大话数据结构_二叉树11/03
- ♥ 大话数据结构_栈_应用11/01
- ♥ 大话数据结构_基础概念11/01
- ♥ 大话数据结构_图表示01/14
- ♥ Dump分析：空指针访问二，重复释放堆内存二03/30
热评文章
- 大话数据结构_栈_应用 0
- BFS和DFS 0
- 大话数据结构_栈 0
- 树总结相关 0
- 大话数据结构_线性表_双向链表 0
- 链表相关 0