1.线性表
2.顺序表
3.链表
4.顺序表和链表的区别和联系
一、线性表
概念:线性表是N个具有相同特性的数据元素的有限序列。线性表是一种在实际中应用广泛的数据结构。
常见的线性表:顺序表,链表,栈 , 队列、字符串等
1.2
描述:线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
二、顺序表
顺序表是用一段物理地址连续的储存单元依次储存数据元素的线性结构,一般情况下采用数组储存,在数组上完成数据的增删查改。
顺序表一般分为:
一.静态顺序表:使用定长数组储存元素。
//1.顺序表的静态储存
#define N 7
typedef int SLDataType; //这里我们用typedef来给int 重命名一下,这个方法很巧妙的
typedef struct SeqList
{SLDataType arr[N]; //定长数组int size; //有效数据的个数
}SeqList;//静态储存我们一般是不用的,可能开辟的空间过小,也可能开辟的空间过大
二.动态顺序表:使用动态开辟的数组储存
//SeqList.h(文件的名字)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//2.动态内存开辟
#define INIT_CAPACITY 4
typedef int SLDataType; //这里我们用typedef来给int 重命名一下,这个方法很巧妙的
typedef struct SeqList
{SLDataType* arr; //动态数组,我们可以根据自己的需求来开辟空间int capacity; //容量空间的大小int size; //有效数据的个数
}SL;//我们对数据的操作无非就这几种:“增删查改”// 1 增
void SLInit(SL* ps); //声明 ,我们这里要先开辟空间之后才可以增
//2 删
void SLDestory(SL* ps); //
//3.我们来打印一下看看自己的操作是否正确
void SLprint(SL* ps);
//4.开始往里边储存数据
void SLpushBack(SL* ps, SLDataType x);
//5 开始往里边删除数据
void SLPopBack(SL* ps);
//SeqList.c
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"// 1 增
void SLInit(SL* ps)
{ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//先开辟了四个(int)类型的空间if (ps->arr == NULL) //数组名就是数组首元素的地址{perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;}// 2 删
//很简单 只需要把我们创建的东西给置零就好
// 把动态创建的内存给free掉
//数据置零即可
void SLDestory(SL* ps)
{free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;}
//3.查看
void SLprint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//4.往里边储存元素
void SLpushBack(SL* ps, SLDataType x)
{if (ps->size == ps->capacity){SLDataType * tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//这里有个坑,这里是开阔的是字节,我们要自己注意一下if (tmp == NULL){perror("realloc fail");return;}ps->arr = tmp; //我们要给其重新赋其地址ps->capacity = 2 * ps->capacity;}//这里边我们还需要考虑,如果储存的元素个数size==capacity的话(临界值),我们就需要来扩大空间了 //ps->arr[ps->size] = x;//ps->size++;储存一个元素就把有效个数++;// (这两者的实现情况是一样) ps->arr[ps->size++] = x;
}//删除储存的元素
void SLPopBack(SL* ps)
{//在删除之前我们,我们要判断一下size的大小必须是为>0的,大于0就可以删,小于0就不可以删除了/*if (ps->size == 0){return; //温柔检查}*///暴力检查assert(ps->size > 0);//ps->arr[ps->size - 1] = 0;ps->size--; //这里我们并不需要通过下标来访问每个元素来给其赋值,只需要把元素对于的那个下标删除掉,数据也会自动被删除}
//text.c
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h";
//1.顺序表的静态储存
//#define N 7
//typedef int SLDataType; //这里我们用typedef来给int 重命名一下,这个方法很巧妙的
//typedef struct SeqList
//{
// SLDataType arr[N]; //定长数组
// int size; //有效数据的个数
//}SeqList;
// //静态储存我们一般是不用的,可能开辟的空间过小,也可能开辟的空间过大2.动态内存开辟
//typedef int SLDataType; //这里我们用typedef来给int 重命名一下,这个方法很巧妙的
//typedef struct SeqList
//{
// SLDataType * arr; //动态数组,我们可以根据自己的需求来开辟空间
// int capacity; //容量空间的大小
// int size; //有效数据的个数
//}SL;//函数的调用void TestSeaList()
{SL s;SLInit(&s); // 增// SLprint(&s); //查SLpushBack(&s, 1);//储存SLpushBack(&s, 2);SLpushBack(&s, 3);SLpushBack(&s, 4);SLpushBack(&s, 5);SLpushBack(&s, 6);SLpushBack(&s, 7);SLpushBack(&s, 8);SLpushBack(&s, 9);SLprint(&s); //查SLPopBack(&s); //删除SLPopBack(&s);SLprint(&s); //查SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);//SLPopBack(&s); //这里我们储存了9个却删除了10个,size= - 1了 ,越界访问了程序直接崩掉SLprint(&s); //查SLpushBack(&s, 10);SLpushBack(&s, 20);SLprint(&s); //查SLDestory(&s);//删 SLInit(&s); // 增,因为这里我们已经置零了一次要增加的话,需要重新的给其开辟空间SLpushBack(&s, 10);SLpushBack(&s, 20);SLprint(&s); //查
}int main()
{TestSeaList();//调用函数return 0;
}
三、链表
概念:链表是一种物理储存结构上非连续、非顺序的储存结构,数据元素的逻辑顺序是通过链表中的指针链接依次实现的。
在逻辑上我们可以分析一下
链表可以用来补充顺序表不能完成的任务
链表的示意图
3.2 链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8中情况
进行组合我们就可以得到8种情况
但是我们经常还是使用以下两种情况
1.无头单向费循环链表
//Slist.h
#pragma once
//放定义
//单链表的实现和使用
//先把常见使用的头文件包含一下
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//struct SlistNode //单链表
//{
// int data;
// struct SlistNode* next;//注意这里我们创建的是一个指针
// // 不过它的类型是struct SlistNode
//};
//这样写太过复杂,而且只能储存int 类型的,不够健壮//我们可以用typedef 来重新命名typedef int SLDataType; //给int类型重新命名typedef struct SlistNode //单链表
{SLDataType data;struct SlistNode* next;//注意这里我们创建的是一个指针// 不过它的类型是struct SlistNode
}SLTNode; //给u结构体类型也重新命名void SLTPintf(SLTNode* phead); // 1.打印的实现SLTNode* BuySLtNode(SLDataType x);//创建结点void SLTPushBack(SLTNode** pphead, SLDataType x);//尾插数据//这里用到了二级指针void SLTPopBack(SLTNode** pphead); //尾删void SLTPushFront(SLTNode** pphead, SLDataType x); //头插void SLTPopFront(SLTNode** pphead); //头删SLTNode* SLTFind(SLTNode* phead, SLDataType x);//找到特定值的位置void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);//插入数据的void SlTErase(SLTNode** pphead, SLTNode* pos);void SLTInsertAfter(SLTNode* pos, SLDataType x);//这里我们是再随机的一个值后边插入值void SLTEraseAfter(SLTNode* pos);//随机删除数据
//Slist.c
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//放声明
//只是访问,并不改变
void SLTPintf(SLTNode* phead) //打印,打印只是用来通过指针来访问每一个数据,不改变指针所以就没必要传二级地址
{SLTNode* cur = phead; //先接收一下起始的指针//while(cur->next != NULL)while (cur) // == while(cur!=NULL){printf("%d->", cur->data);//这一步实现的是打印每个指针对应的值cur = cur->next;//cur++;不能实现,因为这里的地址可能不是连续的}printf("\n");
}
SLTNode* BuySLtNode(SLDataType x)
{//插入数据的前提是我们需要开辟空间SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//这里是为下一个的单链表开辟对的空间if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode; //创建了一个结点}void SLTPushBack(SLTNode** pphead, SLDataType x)//尾插
{assert(pphead);SLTNode* newnode = BuySLtNode(x);if (*pphead == NULL){*pphead = newnode;}else{// 找尾SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
//
//void SLTPushback(SLTNode** pphead, SLDataType x)//尾插
//{
// assert(pphead != NULL);
//
// SLTNode * newnode = BuySLtNode(x); //返回值来接收一个结点
// //这里我们插入数据之前要考虑两种情况
// //1.链表中传入的地址为NULL
// //2.链表中传入的地址不为NULL
// if (*pphead = NULL)
// {
// *pphead = newnode; //这里是把全部的newnode包含的数据和指针都赋值给它
// //这里我们改变的是整个结构体中的内容和指针,如果是传值调用就无法改变,传地址才可以
// }
// else //找尾
// {
// //因为这里是二级指针,我们先来通过解引用拿出指针
// //这里我们只是访问指针,并不需要改变指针,因此并不需要二级指针的参与
//
// // while (tail->next != NULL) //通过地址来依次访问,知道找到NULL时
// // {
// // tail = tail->next;
// // }
// // //当找到空指针的那一刻我们就需要进行把新的链表插入
// // tail->next = newnode;
//
// // 找尾
// SLTNode* tail = *pphead;
// while (tail->next!= NULL) //我们这里只是通过访问链表的指针 并没有改变地址
// {
// tail = tail->next;
// }
//
// tail->next = newnode;//tail->next指向新插入的结点即可
// }
//
//
//}void SLTPopBack(SLTNode** pphead)//尾删,用到了快慢指针
{//二级指针是不可能为NULL的,如果为NULL,则说明错误,因此我们这里就需要来判断一下assert(pphead!=NULL);SLTNode* pre = *pphead;SLTNode* tail = *pphead;// 1 只有一个结点的时候if (pre->next == NULL){*pphead = NULL;//这里我们改变了它的地址,改变一个指针的地址,我们要用的是二级地址,所以这里我们传的就是二级地址}//2 多个结点 ,这里我们就需要用到双指针else{while (tail->next != NULL){pre = tail;tail = tail->next;}free(tail);tail = NULL;//防止野指针pre->next = NULL;//给未结点置零//这里我们还有另一种的解决手段,并不需要到二级指针/* while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*/ //这两种的思想是一样的,但是方法却有所差异}
}void SLTPushFront(SLTNode** pphead, SLDataType x)//头插{assert(pphead != NULL);SLTNode* newnode = BuySLtNode(x); //返回值来接收一个结点
//我们要先把指针指向黑改变了newnode->next = *pphead;//先让原来的新节点变为如今的第二个结点*pphead = newnode;//这里的把原结点的地址赋值给新结点
//这里并不需要考虑*pphead 是否为空的假象,因为及时为空,我们这个代码也可以实现}void SLTPopFront(SLTNode** pphead)//头删 ,我们删除的时候是肯定需要有结点的,不然还删它干嘛{assert(pphead != NULL);//这里我们要先把头指针给储存一下,方便下一步的操作SLTNode* first = *pphead;*pphead = first->next;//换新头结点了free(first);first = NULL;//多个结点和一个结点的操作方法都是一样的}SLTNode* SLTFind(SLTNode* phead, SLDataType x)//找到特定值的位置{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)//pos之前插入数据的{assert(pos && pphead);if (pos = *pphead) //如果只有一个结点,这里我们就是头插就好{SLTPushFront(pphead, x); //}else{SLTNode* pre = *pphead; //先找到前一个位置while (pre->next != pos ){pre = pre->next;}SLTNode * newnode = BuySLtNode(x);//改变指向pre->next = newnode;newnode->next = pos;}}//pos位置删除void SlTErase(SLTNode** pphead, SLTNode* pos){assert(pos && pphead);if (*pphead == pos) //说明只有一个头结点{SLTPopFront(pphead);}else{SLTNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}//先改变指向 ,在freepre->next = pos->next;free(pos);}}void SLTInsertAfter(SLTNode* pos, SLDataType x)//这里我们是在pos的后边插入值{assert(pos);SLTNode* newnode = BuySLtNode(x);//首先要改变一下pos与原来后边的指向newnode->next = pos->next;pos->next = newnode;}void SLTEraseAfter(SLTNode* pos)//删除pos之后数据{//删除pos后边的数据,肯定要保证pos和pos下一个位置不为空assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}
//text.c
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//放调用void Test1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1); SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPintf(plist);SLTPopBack(&plist);SLTPopBack(&plist);SLTPintf(plist);}
void Test2()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1); //这里为什么要传指针的地址呢?SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPintf(plist);SLTPopBack(&plist);SLTPintf(plist);SLTPopBack(&plist);SLTPintf(plist);SLTPopBack(&plist);SLTPintf(plist);SLTPopBack(&plist);SLTPintf(plist);}
void Test3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPintf(plist);SLTPopFront(&plist);SLTPintf(plist);SLTPopFront(&plist);SLTPintf(plist);SLTPopFront(&plist);SLTPintf(plist);SLTPopFront(&plist);SLTPintf(plist);}
void Test4()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPintf(plist);//改变值为2的那个结点变为4SLTNode* ret = SLTFind(plist , 2);ret->data *= 2;SLTPintf(plist);
}
void Test5()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPintf(plist);SLTNode* ret = SLTFind(plist, 2);SlTErase(&plist, ret); //这里我们是删除特定的值ret = NULL; //删除后置零,是为了防止指针泄露SLTPintf(plist);}
void Test6()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTNode* ret = SLTFind(plist, 2);SLTInsertAfter(ret, 10);SLTPintf(plist);SLTEraseAfter(ret);SLTPintf(plist);}int main()
{//Test1();//尾插,尾删//Test2(); //头插,尾删//Test3(); // 尾插 头删//Test4();//尾插 变某个特定的值//Test5(); //删除某个特定的结点Test6();//在某个特定的结点后插入数据,删除数据return 0;
}
2.带头双向循环链表
//List.h
#pragma once
//放定义
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>typedef int LTDataType;typedef struct ListNode
{struct ListNode * prev;struct ListNode * next;LTDataType data;} LTNode;LTNode* LTInit();//先插入一个结点,方便操作void LTDestory(LTNode* phead);//全部删除void LTPrint(LTNode* phead);//打印数据bool LTEmpty(LTNode* phead);//该链表是不是空链表void LTpushBack(LTNode* phead, LTDataType x);//尾插void LTPopBack(LTNode* phead);//尾删void LTPushfront(LTNode* phead, LTDataType x);//头插//void LTPushBack(LTNode* phead);//头删void LTInsert(LTNode* phead, LTDataType x);//随机插入//void LTErase(LTNode* phead);//随机删除
//list.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"LTNode* BuyListNode(LTDataType x) // 这里的返回值不为空是因为我们创建了一个结点目,要把这个结点返回
{LTNode * node = (LTNode *)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");return NULL;//exit(-1);}node->next = NULL;node->prev = NULL;node->data = x;return node;
}LTNode* LTInit()//先插入一个头结点,方便操作,当哨兵位,没有值
{LTNode* phead = BuyListNode(-1);//只有一个结点的时候,要自己指向自己phead->next = phead;//指向头结点phead->prev = phead;//指向尾结点return phead;
}
void LTDestory(LTNode* phead)//全部删除
{assert(phead);LTNode* cur = phead->next;LTNode* cur2 = cur;while (cur != phead){free(cur);cur = NULL;//这一步并没有什么用,形参的改变不会影响实参cur = cur2->next;}
}
void LTPrint(LTNode * phead)//打印数据
{assert(phead);//这里我们要断言的目的是,哨兵位是不可能为0的,如果为0则说明有错误printf("<==>");LTNode* cur = phead->next;//哨兵位的结点是没有值的,所以我们不需要释放while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");//打印完换个行
}
bool LTEmpty(LTNode* phead)// 判断该链表是不是空链表
{//if (phead->next = phead)//{// return true;//}//else//{// return false;//}return phead->next == phead;//这两种方法都可以
}
void LTpushBack(LTNode*phead ,LTDataType x)//尾插
{assert(phead);LTNode* newnode = BuyListNode(x);// 这里我们玩的就是 头phead 尾tail 新结点newnode //LTNode* tail = phead->prev; //这里指向的是phead 的尾结点//tail->next = newnode;//newnode->prev = tail;//phead->prev = newnode;//newnode->next = phead;LTInsert(phead, x);//尾插
}
void LTPopBack(LTNode* phead)//尾删
{assert(phead); //这里需要判断链表中是不是只有一个哨兵的结点assert(!LTEmpty(phead));//这里我们需要的是它为真,继续LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tail = NULL;phead->prev = tailprev;tailprev->next = phead;//这里最重要的是 我们改变了他们的指向}
void LTPushfront(LTNode* phead, LTDataType x)//头插
{assert(phead);LTNode* newnode = BuyListNode(x);//LTNode* first = phead->next;//这一步是先把原来哨兵位的头节点给储存起来,方便下一步使用//newnode = phead->next;//(改变了指向)这一步是把phead尾结点,指向newnode的pre结点//newnode->prev = phead;//指向的phead的next结点 ///但是这个代码是有问题的,不能实现//newnode->next = first;//指向的phead的头结点//first->prev = newnode;// 这里的phead->next,指向的是哨兵位的头结点,因为刚开始的时候,他是自己指向自己的/*newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;*/LTInsert(phead->next,x);//头插}
//void LTPushBack(LTNode* phead)//头删
//
void LTInsert(LTNode* pos, LTDataType x)//随机插入,这里的pos 不能为空(我们一般要从哨兵位的下一个结点开始插入,)
{ //因为哨兵位是没有值的assert(pos);//prev newnode pos 的关系LTNode* pre = pos->prev;LTNode* newnode = BuyListNode(x);pre->next = newnode;newnode->prev = pre;newnode->next = pos;pos->prev = newnode;//这个代码就可以代替头插和尾插
}
void LTErase()//随机删除
//text.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void projecttest()
{LTNode* plist = LTInit(); // 哨兵结点,此时只有哨兵位结点printf("尾插入数据\n");LTpushBack(plist, 1);LTpushBack(plist, 2);LTpushBack(plist, 4);LTpushBack(plist, 15);LTpushBack(plist, 12);LTPopBack(plist);LTPrint(plist); //打印 到这里就没什么问题printf("尾删除后的数据\n");LTPopBack(plist);LTPopBack(plist);LTPopBack(plist);LTPrint(plist);printf("头插入数据\n");LTPushfront(plist, 20);LTPushfront(plist, 21);LTPushfront(plist, 22);LTPrint(plist); //}int main()
{projecttest();return 0;
}
这里我们为大家介绍了循序表和链表大家可以根据情况去写一些题目