赞
踩
顺序表是线性表的一种
所谓线性表指一串数据的组织存储在逻辑上是线性的,而在物理上不一定是线性的
顺序表的底层实现是数组,其由一群数据类型相同的元素组成,其在逻辑与物理上均是线性的。
对于顺序表的结构及各种操作函数的声明
#define _CRT_SECURE_NO_WARNINGS 1 #include <assert.h> #include<string.h> #include<stdlib.h> #include<string.h> #include<assert.h> //顺序表的声明 typedef int Datatype; //规定顺序表的基本元素是什么类型 struct SeqList { Datatype* arr; //顺序表空间的首地址 int size; //顺序表中当前元素的个数 int capacity; //顺序表当前所申请的空间个数,单位为数据类型大小 }; //初始化一个顺序表的声明 void Initialize(struct SeqList* ps); // 插入数据操作 //尾插法 void TailInsert(struct SeqList* ps, Datatype x); //头插法 void HeadInsert(struct SeqList* ps, Datatype x); //在指定位置插入数据 void RanInsert(struct SeqList* ps, int pos, Datatype x); //删除数据操作 //头删法 void HeadDelete(struct SeqList* ps); //尾删法 void TailDelete(struct SeqList* ps); //在指定位置删除数据 void RanInsert(struct SeqList* ps, int pos); //查找数据,返回下标 int Select(struct SeqList* ps, Datatype x); //删除顺序表的声明 void DeleteList(struct SeqList* ps);
对于顺序表及各种操作函数的实现:
#include "seqlist.h" // 初始化一个顺序表 void Initialize(struct SeqList * ps) { //初始化地址 ps->arr = NULL; //NULL在文件string.h中定义 ps->size = ps->capacity = 0; } // 判断空间是否够用,不够的话申请空间 void DeterSpace(struct SeqList* ps) { if (ps == NULL) { perror("ps"); } if (ps->size == ps->capacity) { // 如果并未分配空间,返回 int exsp = ps->capacity == 0 ? 4 : 2 * ps->capacity; ps->capacity = exsp; //将扩展后的空间大小记录下来 Datatype* p1 = NULL; // 扩展空间大小 p1 = realloc(ps->arr, exsp * sizeof(Datatype)); assert(p1); ps->arr = p1; } } //尾插法 void TailInsert(struct SeqList* ps, Datatype x) { if (ps == NULL) { perror("ps"); } //需要先确定空间是否够用? //如果顺序表中的元素个数等于空间大小,则需要扩展空间--申请原来空间两倍的空间 DeterSpace(ps); // 将值插到顺序表末尾 ps->arr[ps->size++] = x; } // 头插法: void HeadInsert(struct SeqList* ps, Datatype x) { //对于头插法,我们也需要判断空间是否足够用 DeterSpace(ps); //在保证了空间之后,将顺序表中数据先往右移动一个元素大小,再进行插入 for (int i = ps->size; i > 0; i--) { ps->arr[i] = ps->arr[i - 1]; } //空出首地址之后: ps->arr[0] = x; //元素的个数也需要++ ps->size++; } // 在指定位置插入一个数据 void RanInsert(struct SeqList *ps,int pos,Datatype x) { assert(ps); assert(pos>=0 &&pos<=ps->size -1); //在指定位置插入一个数据可以由 将此位置及此位置以后的数据往后移动一位,然后再将数据插入此位置 //在此之前要判断空间是否够用 DeterSpace(ps); for (int i = ps->size-1; i >= pos; i--) { ps->arr[i+1] = ps->arr[i]; //将pos在内之后的数据往右移动一位 } ps->arr[pos] = x; ps->size++; } // 头删法 // 即删除顺序表中的首个元素 void HeadDelete(struct SeqList* ps) { for (int i = ps->size - 1; i > 0; i++) { ps->arr[i - 1] = ps->arr[i]; } ps->arr[ps->size - 1] = 0; ps->size--; } // 尾删法 -- 找到最后一个数组元素置为0; void TailDelete(struct SeqList* ps) { //直接通过ps->size找到顺序表中最后一个元素置为0 ps->arr[ps->size - 1] = 0; ps->size--; } // 删除指定位置的数据 void RanInsert(struct SeqList*ps,int pos) { //我们删除指定位置的数据后,可以由在此位置之后的数据整体往前移动来实现 assert(ps); assert(0 <= pos && pos <= ps->size - 1); //在下标pos之前的数据向前移动 for (int i = ps->size - 1; i > pos; i--) { ps->arr[i - 1] = ps->arr[i]; } ps->arr[ps->size - 1] = 0;//将顺序表原来的最后一个元素位置置为0; ps->size--; // 元素个数-1 } // 查找 // 返回相应的下标 int Select(struct SeqList * ps,Datatype x) { assert(ps); for (int i = 0; i < ps->size - 1; i++) { if (ps->arr[i] == x) { return i; } } //找不到返回0 return 0; } // 删除一个顺序表 void DeleteList(struct SeqList* ps) { if (ps == NULL) { exit(1); } free(ps->arr); ps->arr = NULL; //并将元素个数,空间记录清除 ps->size = ps->capacity = 0; }
链表是线性表的一种
1 链表的逻辑结构是线性的,但其物理存储结构不是线性的。
2 链表的基本元素为结点,结点由数据域与指针域组成,数据域中存放存储的数据,
指针域中存放指向其他结点的指针, 结点之间通过指针互相联系。
链表共有8种(2*2*2)
链表的三种特性分别为: 带头与不带头
( 所谓头即指不携带有效数据的头节点)
单向与双向链表
循环与不循环
(所谓循环即第一个结点与尾结点链接在一起)
链表:
最常见的有两种:单链表与双向链表
单链表的全称是不带头单向不循环链表
我在代码中的注释所写的首节点是可以携带有效数据的,为了避免与头节点混淆,所以我用首节点作为名称,而不是头节点!
代码:
#include<stdlib.h> #include<stdio.h> #include<assert.h> // 声明单链表结点 // 对链表中数据类型的声明 typedef int Datatype; typedef struct ListNode { Datatype data; //结点中的数据 struct ListNode* Next;//指向下一个结点的指针 }Node; //打印链表函数声明 void PrintList(Node* ps); //创建新结点并赋值的函数声明 Node* CreateNode(Datatype x); // 插入数据 // 头插 void HeadInsert(Node** phead, Datatype x); //尾插 void TailInsert(Node** phead, Datatype x); // 尾删 void TailDelete(Node** phead); // 头删 void HeadDelete(Node** phead); // 查找 Node* Select(Node* phead, Datatype x); // 在指定位置之前插入数据 void RanLeftInsert(Node** phead, Node* pos, Datatype x); // 在指定位置之后插入数据 // 我们不需要首节点的参数,因为不需要遍历,也不需要在首节点之前插入数据 void RanRightInsert(Node* pos, Datatype x); // 删除pos位置的结点 void DeleteNode(Node** phead, Node* pos); // 删除pos之后的结点 void DeleteAfterNode(Node* pos); // 销毁链表: void Distory(Node** phead);
代码:
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" //打印链表函数 void PrintList(Node* ps) { while (ps!=NULL) { printf("%d\n", ps->data); ps = ps->Next; } } // 创建新结点: Node* CreateNode(Datatype x) { Node* newnode = (Node*)malloc(sizeof(Node)); if (newnode == NULL) { perror("malloc"); exit(1); //退出程序 } newnode->data = x; newnode->Next = NULL; return newnode;//返回新结点的指针 } // 插入数据 // 头插 void HeadInsert(Node ** phead,Datatype x ) { Node* newnode = CreateNode(x); // 将新节点插入到原链表的首部 newnode->Next = *phead; // 将新节点即新链表首节点的地址赋给*phead *phead = newnode; } //尾插 void TailInsert(Node** phead, Datatype x) { //参数为指向 指定链表的首结点 的指针与要插入的数据 //如果链表一开始为空,即phead =NULL时,则ptail->Next则有问题, Node* ptail = *phead; if (* phead == NULL) { * phead = CreateNode(x); //在函数调用结束后,函数中的局部变量会被收回, //形参phead值的改变不会影响到实参,如果采用首节点二重指针 // 则可以通过形参改变首节点的指针。 } else { //先找到尾结点 while (ptail->Next != NULL) { ptail = ptail->Next; } //在找到尾结点后,在尾结点后插入新的结点,并赋值 ptail->Next = CreateNode(x); } } // 尾删 void TailDelete(Node**phead) { //链表不能为空 assert(phead && *phead); //我们在删除尾结点之后,尾结点之前的指针就变为野指针,我们需要找到此指针并置为空 //当链表只有一个结点时: if ((*phead)->Next == NULL) { free(*phead); *phead = NULL; } else { // 创建存放指向尾结点的指针 Node* prev = NULL; Node* ptail = *phead; //查找头节点 while (ptail->Next) {// ptail->Next != NULL; prev = ptail; ptail = ptail->Next; } //在找到尾结点后: free(ptail); ptail = NULL; //将指向尾结点的指针置为空 prev->Next = NULL; } } // 头删 void HeadDelete(Node **phead) { assert(phead && *phead); //链表不能为空 //在删除首节点之后,我们需要能够找到下一个结点的地址 Node* next = (*phead)->Next;//->的优先级比*大 free(*phead); *phead = next; } // 查找 Node* Select(Node* phead, Datatype x) { Node* sel = phead; while (sel) { if (sel->data == x) { return sel; } sel = sel->Next; } } // 在指定位置之前插入数据 void RanLeftInsert(Node**phead,Node *pos,Datatype x) { //因为首节点可能会改变,所以用二级指针作为形参,避免用一级指针无法改变链表的首地址 //在指定位置之前插入数据的情况只有图中的三种情况,在链表之前,在链表中,在链表最后一个元素之前 assert(phead&& *phead); assert(pos); //因为pos不能为空,所以*phead也不能为空,否则*phead为空时,也可以进行头插 if (pos == *phead) { //pos在首节点处,这相当于头插法 HeadInsert(phead, x); } else { //pos位置在链表中与链表最后一个元素上,操作没有本质区别 Node* newnode = CreateNode(x); Node* prev = *phead; while (prev->Next!=pos) { prev = prev->Next; } //当找到了pos之前的prev时: newnode->Next = pos; prev->Next = newnode; } } // 在指定位置之后插入数据 // 我们不需要首节点的参数,因为不需要遍历,也不需要在首节点之前插入数据 void RanRightInsert(Node * pos,Datatype x) { assert(pos); //我们先创建新结点 Node* newnode = CreateNode(x); //将结点插入到pos之后: newnode->Next = pos->Next; pos->Next = newnode; } // 删除pos位置的结点 void DeleteNode(Node** phead, Node* pos) { assert(phead && *phead); assert(pos); //在删除pos结点时,我们需要将pos之后的结点与pos之前的结点链接起来, //pos之后的结点可以用pos->next找到,pos之前的结点需要在遍历时,用变量prev保存! if (pos == *phead) { //当pos是首节点时,此时的情况即头删法 HeadDelete(phead); } else { Node* prev = *phead; //在采用这条判断语句的前提是:pos不是首结点 while (prev->Next != pos) { prev = prev->Next; } //当找到prev时,将pos之后的结点与pos之前的结点链接起来; prev->Next = pos->Next; //释放掉pos free(pos); } } // 删除pos之后的结点 void DeleteAfterNode(Node* pos) { assert(pos && pos->Next); //要删除pos之后的结点,要将pos->next之后的结点与pos链接起来,再删除pos Node* del = pos->Next; pos->Next = del->Next; free(del);//难道此时pos->Next的值不会发生变化? del = NULL; // 兄弟们,下面的c打印的值是多少?它的值会不会随着a的变化而变化呢? //int a = 1; //int c = a; // a++; //printf("%d\n",c); } // 销毁链表: void Distory(Node **phead) { assert(phead && *phead); Node* pcur = *phead; while (pcur != NULL) {//链表的销毁需要一个结点一个结点的释放 Node* next = pcur->Next; free(pcur); pcur = next; } *phead = NULL; }
双向链表的全称是带头双向循环链表
分析图:
#define _CRT_SECURE_NO_WARNINGS 1 #include<string.h> #include<assert.h> #include<stdlib.h> typedef int Datatype; //定义双链表结点的格式 typedef struct ListNode { Datatype data; struct ListNode* next; struct ListNode* prev; }ListNode; //函数操作的声明: // 创建结点 void CreateNode(Datatype x); // 打印链表: void PrintList(ListNode* phead); //初始化链表 void Initialize(ListNode** phead); //插入数据操作 // 尾插法: // 我们不需要改变头节点,所以用一级指针作为形参即可 void TailInsert(ListNode* phead, Datatype x); //头插法 void HeadInsert(ListNode* phead, Datatype x); // 尾删法 void TailDelete(ListNode* phead); //头删: void HeadDelete(ListNode* phead); // 查找 ListNode* Select(ListNode* phead, Datatype x); // 在指定位置之后插入数据 ListNode* AfterSelect(ListNode* pos, Datatype x); //删除指定位置pos节点 //pos的形参是一级而不是二级是因为前面的函数形参皆是一级指针 ,这样保证了接口的一致性,确保了 // 他人的方便调用与解读。 void DeleteNode(ListNode* pos, ListNode* phead); //销毁链表: void Distory(ListNode* phead);
#include"List.h" // 打印链表: void PrintList(ListNode *phead){ //我们遍历双向链表的条件是什么? //我们能够找到判断条件是因为,我们知道双向链表从哪里开始到哪里结束是一个循环,我们只是把自己所知道的 //用符号的形式表述出来,这是一种能力! ListNode* p1 = phead->next; while(p1 !=phead) { printf("%d\n", p1->data); p1 = p1->next; } } //初始化链表 //因为双向链表是带头的【即有头节点】,所以需要先为链表创建一个头节点 void Initialize(ListNode ** phead) { *phead = CreateNode(-1);//创建头节点并随便赋值为1 } //创建新节点并赋值函数 ListNode * CreateNode(Datatype x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = x; //既然双向链表是循环的,我们在创建结点时,可以先使其自循环! newnode->next = newnode; newnode->prev = newnode; return newnode; } //插入数据操作 // 尾插法: // 我们不需要改变头节点,所以用一级指针作为形参即可 void TailInsert(ListNode * phead,Datatype x) { ListNode* newnode = CreateNode(x);//创建一个新结点 //用phead->prev即可找到尾结点 //找到后 phead->prev->next = newnode;//将新节点插入到链表尾部 newnode->next = phead; newnode->prev = phead->prev; phead->prev = newnode; } //头插法 void HeadInsert(ListNode* phead, Datatype x) { ListNode* newnode = CreateNode(x); //指针先动谁? //先操作phead->next指向的结点 //如果先操作phead结点,则在将phead->next指向新节点后,后面的链表部分就找不到位置了 //头插法最多动4个指针:头节点的next,原来第二个结点(可能没有)的prev,新节点的prev与next指针 newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; } // 尾删法 void TailDelete(ListNode * phead) { // 尾删首先要找到尾结点,然后安排好相应的结点 //这是判断链表有效,必须有头节点 assert(phead); //这是判断链表不能为空,否则无法删除 assert(phead->next!=phead); // phead del del->prev //涉及的节点 ListNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; // 删除del节点 free(del); del = NULL; } //头删: void HeadDelete(ListNode* phead) { assert(phead && phead->next != phead); ListNode* del = phead->next; del->next->prev = phead; // 删除节点 free(del); del = NULL; } // 查找 ListNode* Select(ListNode* phead,Datatype x) { ListNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } //没有找到 return NULL; } // 在指定位置之后插入数据 ListNode* AfterSelect(ListNode* pos, Datatype x) { assert(pos); ListNode* newnode = CreateNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; } //删除指定位置pos节点 //pos的形参是一级而不是二级是因为前面的函数形参皆是一级指针 ,这样保证了接口的一致性,确保了 // 他人的方便调用与解读。 void DeleteNode(ListNode * pos,ListNode* phead) { assert(pos && pos != phead); pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; } //销毁链表: void Distory(ListNode*phead) { assert(phead); ListNode* pcur = (phead)->next; while (pcur != NULL) { ListNode* next = pcur->next; free(pcur); pcur = next; } // 此时pcur指向phead,而phead还没有被销毁 free(phead); phead = NULL; //为了接口的一致性,不将形参改为ListNode**类型, //则需要在调用函数后,再将实参赋值为NULL; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。