目录
链表的引入:
上一节我们讲述了顺序表,为什么要继续引入链式表呢？
因为在某些的存储条件中，顺序表会显得很复杂（如下）
(1)插入或删除的运算效率很低。 在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素；
（2）顺序表的顺序存储结构下，顺序表的存储空间不便于扩充；（因为线性表你要提前给他分配空间，如果是不知道空间大小，大了就浪费，小了就不够）
（3）线性表的顺序结构不便于对存储空间的动态分配。
（线性表是静态的，链表是动态的)
那么我们对应的就是引入一种新的存储方式:链表
那么它具有哪些优点呢？
1）插入删除速度快
2）内存利用率高，不会浪费内存(直接现场来进行分配空间的)
3）大小没有固定，拓展很灵活。
在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
1-链表的初始化
在初始化之前，我们先了解什么是链表? 链表长什么样子?
链表:是可以通过一组任意的存储单元来存储线性表的数据元素的,这组存储单元可以是连续的也可以使不连续的.。没错你没听错是任意的。
那么对于这个很牛的存储长什么样子呢?
以及对于头指针，头结点，首元结点的举例:
?
?但是这个却有要求的和顺序表一样:要求头指针只是链式表的第一个结点的地址，最后一个节点没有直接后继，同时指针域必须置空NULL：
那么对于单链表的存储结构的定义如下：
typedef struct Node{
ElemType data; //数据域，其实和那个DATA data 效果是一样的
struct Node *next; //指针域
}LNode, *LinKlist;
在此说明:?// LNode, *LinKlist 都是结构体指针类型，这俩类型等价 ,则一般用LinkList来定义头指针变量，强调的单链表的头指针?，LNode *则定义单链表的任意结点指针变量如果你对结构体和函数指针有疑惑的话，请复习一下.
初始化的定义:?
LinkList Init_List()
{
LNode *L;
L= new LNode; //申请结点的空间
if(L==NULL) //判断是有有足够空间
printf("申请空间内存失败\n");
L->next = NULL; //将next设置成NULL,初始长度为0 的单链表
return L;
}2-建立一个单链表
建立链表的形式是具有两种的1-头插法建立单链表 2-尾插法建立单链表，那么我们就说一个头插法建立单链表.代码如下:
LinkList Create_ListH()
Elemtype x;
LInkList L;
LNode *p; //节点的指针
L= new LNode; //申请头结点空间
L->next = NULL; //初始化空链表
while(scanf("%d",&x) != EOF){
//EOF一般是在宏定义中事前定义好的，多数值为-1
p= new LNode;
p->data=x; //数据域，先将x的值储存在结点中
p->next = L->next; //将节点插入到表头
L->next = p;
}
return L;
}
有没有什么疑惑呢？ 对于while循环中的数据
while(scanf("%d",&x) != EOF){
? ? ? ? ? ? ? ? ? ? ? ? ?//EOF一般是在宏定义中事前定义好的，多数值为-1
p= new LNode;
p->data=x; //数据域，先将x的值储存在结点中
p->next = L->next; ?//将节点插入到表头
L->next = p;}
但是对于前插还具有特点,比如说你每次将数据进行插入的时候都会向后进行排序，因为你每次都插在链表的头部,然后所得链表的逻辑顺序和输入元素的顺序相反,头插链表也称之为逆序的建表.
?那换个想法吧，把这个链表先扩大，不要想着是一个空链表的形式
?按照上边的代码把空链表想成他并不是一个空链表的形式，依旧是头插入，:
?以下是完整的单链表的建立.
ChainListType* ChainListAddEnd(ChainListType* head, DATA data)
{
ChainListType* node, * h;
if (!(node = (ChainListType*)malloc(sizeof(ChainListType))))
{
printf("未保留结点数据申请内存失败!\n");
return NULL;
}
node->data = data;
node->next = NULL;
if (head == NULL)
{
head = node;
return head;
}
h = head;
while (h->next != NULL)
h = h->next;
h->next = node;
return head;
}
3-插入运算
数据的插入其实遵循以下几个步骤:
- 生成数据域为x的新节点,指针q指向新的结点
- 从头结点开始，找到元素ai所在结点，使指针p指向该结点
- 插入新节点输入ai所在结点之.
- 若i=-1，则表示将信结点插入在a0之前
- 若i>-1，则表示将新节点插入在单链表的中间位置:
- 表长要加一
怎么说,其实图还是那个刚才的那个,一样的只不过刚才是在头结点的时候，将其先放大,现在是最初的模样.
先说说书上的吧,
LinkList Insert_List(LinkList L,int i,ElemType x){
LNode *q,*s;
int j=0;
q=L;
while(q&&j<i-1){
q=q->next； //为啥找打前驱结点呢？
j++;
}
s=new LNode;
s->data=x
s->next = q->next;
q->next=s;
return L;
}?
：因为我们知道在单链表中，若果在某一个结点后插入一个新的结点，则需要相机修改两个指针域的值，很明显就是直接前驱和直接后继 ，因为你要该表指针域的指向把你新加的的结点给加入进去，使得前驱结点现在指向加入的结点，然后加入的结点指向原前驱结点所指向的结点，这样位置就穿插进来了.
ChainListType* ChainListInsert(ChainListType* head, char* findkey, DATA data)
{
ChainListType* node, * node1;
if (!(node = (ChainListType*)malloc(sizeof(ChainListType))))
{
printf("未保留结点数据申请内存失败!\n");
return 0;
}
node->data = data;
node1 = ChainListFind(head, findkey);
if (node1)
{
node->next = node1->next;
node1->next = node;
}
else {
free(node);
printf("未找到插入位置!\n");
}
return head;
}?
4-删除运算
在经过上面那个多学习中，对于删除运算有没有什么想法呢？
有吧，就是使得前驱结点指向后继的后继，使得吧你想从删除的那个那个直接给忽视掉们就能达到删除的效果,
p->next=p->next->next;int ChainListDelete(ChainListType* head, char* key)
{
ChainListType* node, * h;
node = h = head;
while (h)
{
if (strcmp(h->data.key, key) == 0) //看看查找的是否匹配，然后进行删除
{
node->next = h->next;
free(h); //直接给释放了，但是有的用的是delete
return 1;
}
else {
node = h;
h = h->next; //h指向h的直接后继结点
}
}
return 0;
}5-求表长
对于表长的计算，其实在顺序表中我们是自己去直接定义表的长度，但是在链表中要进行有效的计算，具体如下
int Lnegth_List(LinkList L){
Lnode *p;
int i=0;
p->L;//指向表头
while(p->next){ //如果到最后（表尾的时候，则为NULL终止循环）
p=->next; //来进行往后走啊走啊
i=+;
}
return i;
}
6-查找运算
链表的节点与节点之间唯一的联系就是指针域的指向，所以我们在查找某一个元素的时候要按照指针域来进行逐个的搜索,也就是顺着next来进行结点的搜索.
观察下面的代码，h其实一直是在变化的，当在if循环中如果两个char类型完全一样的时候就直接返回h了，如果不是则就h=h->next,来指向下一结点,一直在while循环里循环，如果到最后循环结束，其实h也是为NULL.
ChainListType* ChainListFind(ChainListType* head, char* key)
{
ChainListType* h;
h = head;
while (h)
{
if (strcmp(h->data.key, key) == 0)
return h;
h = h->next;
}
return NULL;
}
那么说了那么多了,让我们看看实际的演示效果图吧代码虽然有点不一样，但是指针域的使用方向是大体差不多的.
?其实是能达到一定的效果的.完全代码如下.
ChainList.cpp
#include "ChainList.h"
#include <string.h>
#include <corecrt_malloc.h>
ChainListType* ChainListAddEnd(ChainListType* head, DATA data)
{
ChainListType* node, * h;
if (!(node = (ChainListType*)malloc(sizeof(ChainListType))))
{
printf("未保留结点数据申请内存失败!\n");
return NULL;
}
node->data = data;
node->next = NULL;
if (head == NULL)
{
head = node;
return head;
}
h = head;
while (h->next != NULL)
h = h->next;
h->next = node;
return head;
}
ChainListType* ChainListFirst(ChainListType* head, DATA data)
{
ChainListType* node, * h;
if (!(node = (ChainListType*)malloc(sizeof(ChainListType))))
{
printf("未保留结点数据申请内存失败!\n");
return NULL;
}
node->data = data;
node->next = head;
head = node;
return head;
}
ChainListType* ChainListFind(ChainListType* head, char* key)
{
ChainListType* h;
h = head;
while (h)
{
if (strcmp(h->data.key, key) == 0)
return h;
h = h->next;
}
return NULL;
}
ChainListType* ChainListInsert(ChainListType* head, char* findkey, DATA data)
{
ChainListType* node, * node1;
if (!(node = (ChainListType*)malloc(sizeof(ChainListType))))
{
printf("未保留结点数据申请内存失败!\n");
return 0;
}
node->data = data;
node1 = ChainListFind(head, findkey);
if (node1)
{
node->next = node1->next;
node1->next = node;
}
else {
free(node);
printf("未找到插入位置!\n");
}
return head;
}
int ChainListDelete(ChainListType* head, char* key)
{
ChainListType* node, * h;
node = h = head;
while (h)
{
if (strcmp(h->data.key, key) == 0)
{
node->next = h->next;
free(h);
return 1;
}
else {
node = h;
h = h->next;
}
}
return 0;
}
int ChainListLength(ChainListType* head)
{
ChainListType* h;
int i = 0;
h = head;
while (h)
{
i++;
h = h->next;
}
return i;
}
ChainLish.h
#include <stdio.h>
typedef struct
{
char key[15];
char name[20];
int age;
}DATA;
typedef struct Node
{
DATA data;
struct Node* next;
}ChainListType;
ChainListType* ChainListAddEnd(ChainListType* head, DATA data);
ChainListType* ChainListFirst(ChainListType* head, DATA data);
ChainListType* ChainListFind(ChainListType* head, char *key);
ChainListType* ChainListInsert(ChainListType* head, char* findkey,DATA data);
int ChainListDelete(ChainListType* head, char* key);
int ChainListLength(ChainListType* head);ChainList。main函数部分
//这个是写链表的main函数部分
#include <stdio.h>
#include "ChainList.h"
#include <string.h>
void ChainListAll(ChainListType* head)
{
ChainListType* h;
DATA data;
h = head;
printf("链表所有数据如下：\n");
while (h)
{
data = h->data;
printf("(%s,%s,%d)\n", data.key, data.name, data.age);
h = h->next;
}
return;
}
int main()
{
ChainListType* node, * head = NULL;
DATA data;
char key[15], findkey[15];
printf("输入链表的数据,包括一些关键字，姓名，年龄,输入0则退出\n");
do {
fflush(stdin);
scanf("%s", data.key);
if (strcmp(data.key, "0") == 0) break;
scanf("%s%d", data.name, &data.age);
head = ChainListAddEnd(head, data);
} while (1);
printf("该链表共有%d个结点.\n", ChainListLength(head));
ChainListAll(head);
printf("\n插入结点,输入插入位置的关键字:");
scanf("%s", &findkey);
printf("输入插入结点的数据（关键字 姓名 年龄):");
scanf("%s%s%d", data.key, data.name, &data.age);
head = ChainListInsert(head, findkey, data);
ChainListAll(head);
printf("\n在链表中查找,输入查找关键字:");
fflush(stdin);
scanf("%s", key);
node = ChainListFind(head, key);
if (node)
{
data = node->data;
printf("关键字%s对应的结点数据源为(%s,%s,%d)\n",key, data.key, data.name, data.age);
}
else
printf("在链表中未找到关键字为%s的结点！\n", key);
printf("\n在链表中删除结点,输入要删除的关键字：");
fflush(stdin);
scanf("%s", key);
ChainListDelete(head,key);
ChainListAll(head);
getchar();
return 0;
}
那就分享到这了
引用文章作者如下:https://blog.csdn.net/nsjlive/article/details/88032748