数据结构(王道版本，主讲人:闲鱼学长)P7-P18
带头结点 
带头结点 
发布日期：2021-05-06 03:14:48
浏览次数：39
分类：精选文章
本文共 15515 字，大约阅读时间需要 51 分钟。
2.1.1 线性表的定义和基本操作
2.2.1 顺序表的定义
#include#define MaxSize 10//定义最大长度typedef struct { int data[MaxSize];//用静态的“数组”存放数据元素 int length;//顺序表的当前长度}SqList;//顺序表的类型定义void InitSize(SqList& L);//初始化一个顺序表void main(){ SqList L;//声明一个顺序表 InitSize(L);//初始化顺序表 for (int i = 0; i < L.length; i++) { printf("date[%d]=%d\n", i, L.data[i]); }}void InitSize(SqList& L)//初始化一个顺序表{ for (int i = 0; i < MaxSize; i++) { L.data[i] = i;//将所有数据元素设置为默认初始值 } L.length = 10;//顺序表的初始长度为10}//date[0] = 0//date[1] = 1//date[2] = 2//date[3] = 3//date[4] = 4//date[5] = 5//date[6] = 6//date[7] = 7//date[8] = 8//date[9] = 9
2.2.2 顺序表的插入和删除
#include#define MaxSize 6typedef struct{ int data[MaxSize]; int length;}SqList;void InitList(SqList& L){ for (int i = 0; i < 5; i++) { L.data[i] = i * 2; printf("%d ", L.data[i]); } printf("\n"); L.length = 5;}bool ListInsert(SqList& L, int i, int e){ if (i >= 1 && i <= L.length + 1) { for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1];//L.data[5]=L.data[4] L.data[4]=L.data[3] L.data[3]=L.data[2] } L.data[i - 1] = e;//L.data[2]=3; L.length++; return true; } else { return false; }}int main(){ SqList L; InitList(L); if (ListInsert(L, 3, 3)==true) { for (int i = 0; i < L.length; i++) { printf("%d ", L.data[i]); } } else { printf("插入错误"); } return 0;}//0 2 4 6 8//0 2 3 4 6 8
#include#define MaxSize 5typedef struct{ int data[MaxSize]; int length;}SqList;void InitList(SqList& L){ for (int i = 0; i < 5; i++) { L.data[i] = i * 2; printf("%d ", L.data[i]); } printf("\n"); L.length = 5;}bool ListDelect(SqList& L, int i, int &e){ if (i >= 1 && i < L.length + 1) { e = L.data[i - 1]; for (int j = i; j
2.2.3 顺序表的查找
#include#define MaxSize 10typedef struct{ int data[MaxSize]; int length;}SeqList;void InitList(SeqList &L){ L.length = 6; for (int i = 0; i < L.length; i++) { L.data[i] = i;//0 1 2 3 4 5 }}int GetElem(SeqList& L, int i){ return L.data[i - 1];}void main(){ int result; SeqList L; InitList(L); result=GetElem(L, 3); printf("该位置的元素为:%d", result);}//该位置的元素为:2
#include#include #define InitSize 10typedef struct{ int* data; //动态分配 int MaxSize; int length;}SqList;void InitList(SqList& L){ //用malloc函数申请一片连续的存储空间 L.data = (int*)malloc(InitSize * sizeof(int)); L.length = 0; L.MaxSize = InitSize;}int GetLem(SqList L, int i){ return L.data[i - 1]; //和访问普通数组方法一样}void main(){ int result; SqList L; InitList(L); for (int i = 0; i < 5; i++) { L.data[i] = i; } result=GetLem(L,3); printf("该位置的元素为:%d\n", result); free(L.data);}//该位置的元素为:2
#include#include #define InitSize 10typedef struct{ int* data; int MaxSize; int length;}SeqList;void InitList(SeqList &L){ //用malloc函数申请一片连续的存储空间 L.data = (int*)malloc(InitSize * sizeof(int)); L.length = 5; L.MaxSize = InitSize;}int LocateElem(SeqList L, int e){ for (int i = 0; i < L.length; i++) { if (L.data[i] == e) { return i + 1;//数组下标为i的元素值为e，返回其位序i+1 } } return 0;//退出循环，说明查找失败}void main(){ int result; SeqList L; InitList(L); for (int i = 0; i < L.length; i++) { L.data[i] = i; } result=LocateElem(L, 2); printf("该元素在第%d位置\n", result); free(L.data);}//该元素在第3位置
2.3 链表
2.3.1单链表的定义
2.3.2单链表的插入和删除
//在第i个位置插入元素e（带头结点）typedef struct LNode{ Elemtype data; struct LNode *next;}LNode,*LinkList;bool ListInsert(LinkList &L,int i,Elemtype e){ if(i<1) return false; LNode *p;//指针p指向当前扫描到的结点 int j=0;//当前p指向的是第几个结点 p=L;//L指向头结点，头结点是第0个结点 while(p!=NULL&&j next; j++; } if(p==NULL)return false; LNode *s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return true;} 
//在第i个位置插入元素e（不带头结点）typedef struct LNode{ Elemtype data; struct LNode *next;}LNode,*LinkList;bool ListInsert(LinkList &L,int i,Elemtype e){ if(i<1) return false; if(i==1){ //插入第1个结点的操作与其他结点操作不同 LNode *s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=L; L=s;//头指针指向新结点 return true; } LNode *p;//指针p指向当前扫描到的结点 int j=1;//当前p指向的是第几个结点 p=L;//p指向第1个结点（不是头结点） while(p!=NULL&&j next; j++; } if(p==NULL)return false; LNode *s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return true;} 
//后插操作：在p结点之后插入元素e typedef struct LNode{ Elemtype data; struct LNode *next;}LNode,*LinkList;bool InsertNextNode(LNode *p,Elemtype e){ if(p==NULL) return false; LNode *s=(LNode *)malloc(sizeof(LNode)); //某些情况下可能分配失败，如内存不足 if(s==NULL) return false; s->data=e; s->next=p->next; p->next=s; return true; } 
//指定结点的前插操作 //前插操作：在p结点之前插入元素e typedef struct LNode{ Elemtype data; struct LNode *next;}LNode,*LinkList;bool ListInsert(LNode *p,Elemtype e){ if(p==NULL) return false; LNode *s=(LNode *)malloc(sizeof(LNode)); //某些情况下可能分配失败，如内存不足 if(s==NULL) return false; s->next=p->next; p->next=s;//新结点s连接到p之后 s->data=p->data;//将p中元素复制到s中 p->data=e;//p中元素覆盖为e return true; } 
#include#include typedef struct LNode { int data;//数据域 struct LNode* next;//指针域}LNode, * LinkList;//尾插法建立单链表LinkList List_TailInsert(LinkList &L){ int i; L = (LinkList)malloc(sizeof(LNode)); LNode* s, * r = L; printf("请输入你要存储的数据，999为退出输入:\n"); scanf_s("%d",&i); while (i != 999) { s = (LNode*)malloc(sizeof(LNode)); s->data = i; r->next = s; r = s; scanf_s("%d", &i); } r->next = NULL; return L;}//判空bool Empty(LinkList L) { if (L->next == NULL) { printf("表空.\n"); return true; } else { printf("表创建成功.\n"); printf("尾插法建立的单链表如下:\n"); return false; }}//打印输入的单链表的值void test(LNode* L) { LinkList p; p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n");}//按位序删除(带头结点)bool LiseDelete(LinkList& L, int m, int &e) { printf("请输入删除的位置:"); scanf_s("%d", &m); if (m < 1) { printf("删除位置不合法\n"); return false; } LNode* p; int j = 0; p = L; while (p != NULL && j < m - 1) { p = p->next; j++; } if (p == NULL) { return false; } if (p->next == NULL) { return false; } LNode* q = p->next; e = q->data; p->next = q->next; free(q);}//主函数void main() { int m = 0; int e = 0; LinkList L; List_TailInsert(L); Empty(L); test(L); LiseDelete(L, m, e); printf("该位置的元素为：%d\n", e); printf("得到的新的单链表为："); test(L);}//请输入你要存储的数据，999为退出输入://23 54 56 87 999//表创建成功.//尾插法建立的单链表如下 :// 23 54 56 87// 请输入删除的位置 : 3// 该位置的元素为：56// 得到的新的单链表为：23 54 87
不带头结点
#include#include typedef struct LNode { int data;//数据域 struct LNode* next;//指针域}LNode, * LinkList;/*不带头结点的单链表的创建(头插法)*/LinkList LinkCreate(LinkList& L) { LNode* p; int a; L = NULL; printf("请输入数据:"); scanf_s("%d", &a); while (a != 999) { //数据为9999时，停止输入 p = (LNode*)malloc(sizeof(LNode)); p->data = a; p->next = L; L = p; scanf_s("%d", &a); //连续输入数据 } return L;}//判空bool Empty(LinkList L) { if (L == NULL) { printf("表空.\n"); return true; } else { printf("表创建成功.\n"); printf("尾插法建立的单链表如下:\n"); return false; }}//打印输入的单链表的值void test(LNode* L) { while (L!= NULL) { printf("%d ", L->data); L = L->next; } printf("\n");}//按位序删除(不带头结点)bool LiseDelete(LinkList& L, int m, int& e) { printf("请输入删除的位置:"); scanf_s("%d", &m); if (m < 1) { printf("删除位置不合法\n"); return false; } LNode* p; int j = 1; p = L; while (p != NULL && j < m - 1) { p = p->next; j++; } if (p == NULL) { return false; } if (p->next == NULL) { return false; } LNode* q = p->next; e = q->data; p->next = q->next; free(q);}//主函数void main() { int m = 0; int e = 0; LinkList L; LinkCreate(L); Empty(L); test(L); LiseDelete(L, m, e); printf("该位置的元素为：%d\n", e); printf("得到的新的单链表为："); test(L);}//请输入数据:23 54 56 87 999//表创建成功.//尾插法建立的单链表如下 :// 87 56 54 23// 请输入删除的位置 : 3// 该位置的元素为：54// 得到的新的单链表为：87 56 23
//删除指定结点pbool Delete(LNode *p){ if(p==NULL) return false; LNode *q=p->next; p->data=p->next->data; p->next=q->next; free(q); return true;} 
2.3.3单链表的查找
#include#include typedef struct LNode { int data;//数据域 struct LNode* next;//指针域}LNode, * LinkList;//尾插法建立单链表LinkList List_TailInsert(LinkList &L){ int i; L = (LinkList)malloc(sizeof(LNode)); LNode* s, * r = L; printf("请输入你要存储的数据，999为退出输入:\n"); scanf_s("%d",&i); while (i != 999) { s = (LNode*)malloc(sizeof(LNode)); s->data = i; r->next = s; r = s; scanf_s("%d", &i); } r->next = NULL; return L;}//判空bool Empty(LinkList L) { if (L->next == NULL) { printf("表空.\n"); return true; } else { printf("表创建成功.\n"); printf("尾插法建立的单链表如下:\n"); return false; }}//打印输入的单链表的值void test(LNode* L) { LinkList p; p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n");}//按位序查找(带头结点)LNode* GetElem(LinkList L, int i) { printf("请输入查找的位置:"); scanf_s("%d", &i); if (i < 0) { return NULL; } LNode* p; int j = 0; p = L; while (p != NULL && j < i) { p = p->next; j++; } return p;}//主函数void main() { int m = 0; int i = 0; LNode* result; LNode* L = NULL; List_TailInsert(L); Empty(L); test(L); result=GetElem(L,i); printf("该位置的元素为:%d", *result);}//请输入你要存储的数据，999为退出输入://23 32 54 75 87 999//表创建成功.//尾插法建立的单链表如下 :// 23 32 54 75 87// 请输入查找的位置 : 3// 该位置的元素为:54
2.3.4单链表的建立
带头结点 #include#include typedef struct LNode { int data;//数据域 struct LNode* next;//指针域}LNode, * LinkList;//尾插法建立单链表LinkList List_TailInsert(LinkList &L){ int i; L = (LinkList)malloc(sizeof(LNode)); LNode* s, * r = L; printf("请输入你要存储的数据，999为退出输入:\n"); scanf_s("%d",&i); while (i != 999) { s = (LNode*)malloc(sizeof(LNode)); s->data = i; r->next = s; r = s; scanf_s("%d", &i); } r->next = NULL; return L;}//判空bool Empty(LinkList L) { if (L->next == NULL) { printf("表空.\n"); return true; } else { printf("表创建成功.\n"); printf("尾插法建立的单链表如下:\n"); return false; }}//打印输入的单链表的值void test(LNode* L) { LinkList p; p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n");}//指定结点后插bool InsertNextNode(LNode* p, int e) { if (p == NULL) { printf("插入位置不合法"); return false; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true;}//按位序插入(带头结点插入)bool ListInsert(LinkList& L, int m, int n) { printf("请输入插入的位置:"); scanf_s("%d", &m); if (m < 1) { printf("插入位置不合法\n"); return false; } LNode* p; int j = 0; p = L; while (p != NULL && j < m - 1) { p = p->next; j++; } //指定结点后插 printf("插入的值为："); scanf_s("%d", &n); return InsertNextNode(p, n);}//主函数void main() { int m = 0; int n = 0; LinkList L; List_TailInsert(L); Empty(L); test(L); ListInsert(L, m, n); printf("得到的新的单链表为：\n"); test(L);}//请输入你要存储的数据，999为退出输入://23 32 4232 32 999//表创建成功.//尾插法建立的单链表如下 :// 23 32 4232 32// 请输入插入的位置 : 2// 插入的值为：32// 得到的新的单链表为：// 23 32 32 4232 32
不带头结点
#include#include typedef struct Node { int data; //数据域 struct Node* next; //指针域}LNode, * LinkList; //单链表节点类型//尾插法void LinkCreate(LinkList& L) { int a; L = NULL; LNode* p, * r = L; printf("请输入数据:"); scanf_s("%d", &a); while (a != 999) { p = (LNode*)malloc(sizeof(LNode)); p->data = a; p->next = NULL; if (L == NULL) { L = p; r = L; } else { r->next = p; r = p; } scanf_s("%d", &a); }}//单链表的输出void display(LinkList L) { printf("表中数据输出："); while (L != NULL) { printf("%d ", L->data); L = L->next; } printf("\n");}//指定结点后插bool InsertNextNode(LNode* p, int e) { if (p == NULL) { printf("插入位置不合法"); return false; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true;}//按位序插入(带头结点插入)bool ListInsert(LinkList& L, int m, int n) { printf("请输入插入的位置:"); scanf_s("%d", &m); if (m < 1) { printf("插入位置不合法\n"); return false; } if (m == 1) { //插入第1个结点的操作与其他结点操作不同 LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = n; s->next = L; L = s;//头指针指向新结点 return true; } LNode* p; int j = 1; p = L; while (p != NULL && j < m - 1) { p = p->next; j++; } //指定结点后插 printf("插入的值为："); scanf_s("%d", &n); return InsertNextNode(p, n);}int main() { int m = 0; int n = 0; LinkList L; LinkCreate(L); display(L); ListInsert(L, m, n); printf("得到的新的单链表为：\n"); display(L); return 0;}//请输入数据:12 43 65 76 87 999//表中数据输出：12 43 65 76 87//请输入插入的位置 : 3//插入的值为：432//得到的新的单链表为：//表中数据输出：12 43 432 65 76 87
带头结点 #include#include typedef struct LNode { int data;//数据域 struct LNode* next;//指针域}LNode, * LinkList;//头插法建立单链表LinkList List_HeadInsert(LinkList& L) { LNode* s; int i; L = (LNode*)malloc(sizeof(LNode));//创建头结点 L->next = NULL; //头结点的指针域设置为null printf("请输入你要存储的数据，999为退出输入:\n"); scanf_s("%d", &i); while (i != 999) { s = (LNode*)malloc(sizeof(LNode)); s->data = i; s->next = L->next; //实质就是s的后继指针域置为NULL，之所以写L->next是为了实现头插循环 L->next = s; scanf_s("%d", &i); } return L;}//判空bool Empty(LinkList L) { if (L->next == NULL) { printf("表空.\n"); return true; } else { printf("表创建成功.\n"); printf("头插法建立的单链表如下:\n"); return false; }}//打印输入的单链表的值void test(LNode* L) { LinkList p; p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n");}//按位序插入(带头结点插入)bool ListInsert(LinkList& L, int m, int n) { printf("请输入插入的位置:"); scanf_s("%d", &m); if (m < 1) { printf("插入位置不合法\n"); return false; } LNode* p; int j = 0; p = L; while (p != NULL && j < m - 1) { p = p->next; j++; } //指定结点后插 if (p == NULL) { printf("插入位置不合法"); return false; } printf("插入的值为："); scanf_s("%d", &n); LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = n; s->next = p->next; p->next = s; printf("得到的新的单链表为：\n"); test(L); return true;}//主函数void main() { int m = 0; int n = 0; LinkList L; List_HeadInsert(L); Empty(L); test(L); ListInsert(L, m, n);}//请输入你要存储的数据，999为退出输入://23 324 432 655 999//表创建成功.//头插法建立的单链表如下 :// 655 432 324 23// 请输入插入的位置 : 3// 插入的值为：99// 得到的新的单链表为：// 655 432 99 324 23
不带头结点
#include#include //单链表的结构体typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;/*不带头结点的单链表的创建(头插法)*/LinkList LinkCreate(LinkList& L) { LNode* p; int a; L = NULL; printf("请输入数据:"); scanf_s("%d", &a); while (a != 999) { //数据为9999时，停止输入 p = (LNode*)malloc(sizeof(LNode)); p->data = a; p->next = L; L = p; scanf_s("%d", &a); //连续输入数据 } return L;}//判空bool Empty(LinkList L) { if (L == NULL) { printf("表空.\n"); return true; } else { printf("表创建成功.\n"); printf("头插法建立的单链表如下:\n"); return false; }}//单链表的输出void display(LinkList L) { printf("表中数据输出："); while (L != NULL) { printf("%d ", L->data); L = L->next; } printf("\n");}//指定结点后插bool InsertNextNode(LNode* p, int e) { if (p == NULL) { printf("插入位置不合法"); return false; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true;}//按位序插入(带头结点插入)bool ListInsert(LinkList& L, int m, int n) { printf("请输入插入的位置:"); scanf_s("%d", &m); if (m < 1) { printf("插入位置不合法\n"); return false; } if (m == 1) { //插入第1个结点的操作与其他结点操作不同 LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = n; s->next = L; L = s;//头指针指向新结点 return true; } LNode* p; int j = 1; p = L; while (p != NULL && j < m - 1) { p = p->next; j++; } //指定结点后插 printf("插入的值为："); scanf_s("%d", &n); return InsertNextNode(p, n);}/*主函数*/int main() { int m = 0; int n = 0; LinkList L; LinkCreate(L); Empty(L); display(L); ListInsert(L, m, n); printf("得到的新的单链表为：\n"); display(L); return 0;}//请输入数据:23 32 4232 32 999//表创建成功.//头插法建立的单链表如下 :// 表中数据输出：32 4232 32 23// 请输入插入的位置 : 2// 插入的值为：124// 得到的新的单链表为：// 表中数据输出：32 124 4232 32 23
2.3.5双链表的定义
2.3.6循环链表的定义
2.3.7静态链表的定义
2.3.8顺序表和链表的对比
发表评论
最新留言
路过，博主的博客真漂亮。。
[***.116.15.85]2025年04月16日 20时31分27秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
.NET CORE(C#) WPF 重新设计Instagram
2019-03-05
.NET CORE(C#) WPF 方便的实现用户控件切换（祝大家新年快乐）
2019-03-05
C# WPF开源控件库：MahApps.Metro
2019-03-05
使用QT实现一个简单的登陆对话框（纯代码实现C++）
2019-03-05
QT ：warning LNK4042: 对象被多次指定;已忽略多余的指定
2019-03-05
GLFW 源码 下载-编译-使用/GLAD配置
2019-03-05
针对单个网站的渗透思路
2019-03-05
Typescript 学习笔记六：接口
2019-03-05
Scala字符串与容器
2019-03-05
关于JTAG，你知道的和不知道的都在这里
2019-03-05
web服务器-并发服务器2
2019-03-05
【SqlServer】如何把本地SqlServer数据库部署到远程服务器上
2019-03-05
【ASP.NET】ASP.NET中权限验证使用OnAuthorization实现
2019-03-05
第9章 用户自己建立数据类型
2019-03-05
02、MySQL—数据库基本操作
2019-03-05
RedHat Linux-配置YUM仓库
2019-03-05
Redis数据类型
2019-03-05
1907: 树的路径覆盖
2019-03-05
OpenJDK1.8.0 源码解析————HashMap的实现(一)
2019-03-05
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 457549521 位访客