数据结构第二章C语言 —— 单链表
数据结构第二章C语言 —— 单链表
1.什么是单链表
在线性表中，经常遇到储存信息的地方并不连续。一个一个存储单元的地方需要指针（像铁锁连环一样联系起来）这样我们就把存储单位存储的信息和指向下一个地方的指针称为结点。它包括两个域，存储数据元素信息的叫做数据域，存储直接后继存储位置的域称为指针域。指针域中存储的信息叫做指针或链，n个节点链结成一个链表。因为该链表只有一个节点域，所以又称之为单链表或线性链表。
我们现在讨论的单链表都有一个头指针，该指针只有一个结点域，指向第一个结点。
typedef struct {
ElemType data; //结点的数据域Elemtype的用法我的上一篇线性表中有
struct Lnode *next; //结点的指针域，其类型为指向结点的指针类型Lnode*
}Lnode,*LinkList; //定义了两个名字，本质完全一样
头指针的作用：
1>便于首元结点的处理；
2>便于空表和非空标的统一处理；
2.单链表基本操作的实现
2.1单链表的初始化
步骤：
1>生成新结点作为头结点，用头指针L指向头结点。
2>头结点的指针域置空
int InitList(LinkList &L)
{
L=new LNode;//生成新结点作为头结点，用头指针L指向头结点。
L->next = NULL;//头结点的指针域置空
return OK;
}
2.2单链表的取值
查找第i个结点，因为链表中没有直接的顺序去查找，所以必须通过链表的首元结点出发，沿着链域next逐个结点向下访问。
步骤：
1>p指向下一个结点，计数器的值加1.
2>推出循环时，如果指针指的时NULL,或者j>i说明指定的序号i值不合法（i大于n或者i<1)返回ERROR;如果取值成功j=i;就用e保存当前结点的数据域，返回OK
void GetElem(LinkList L,int i,ElemType &e)//e为用来返回找到结点的结点
{
p = L->next;int j = 1;//初始化，p指向首元结点，计数器j给初值1
while(p&&j<i)//p不为空并且查找对象没超出范围
{
p = p->next;//p指向下一个结点
j++;//计数器＋1
}
if(!p||j>i)//i的值不合法，i<=0或i>n
return ERROR;//返回ERROR
e = p->data;//e来存储找到的数据域
return OK;
}
2.3单链表的查找
和单链表的取值差不多，不过那个是找值，这个是值所对应的序号
步骤：
1>用指针p指向首元结点
2>以此顺着链域next向下查找，只要指向当前结点的指针p不为空或者p所指结点的数据域不等于给定值e，则p指向下一个结点。
3>若成功，返回p此时指向结点的地址值，若失败，p的值为NULL
void getelem(LinkList L, ELemType e)
{
p = L->next;
while(p&&p->data!=e)
p = p->elem;
return p;//成功为p失败为NULL
}
2.4单链表的插入
这里的单链表比顺序表麻烦些，但是理解后单链表插入的实现比线性表方便多了
关键部分，a指向下一部分的指针要先给新给的结点。指向新节点的地址再给旧的结点，就像上图一样。
步骤：
1>查找结点ai-1；
2>生成新结点s
3>将新结点*e的数据域置为给定的e
4>a指向下一部分的指针要先给新给的结点。
5>指向新节点的地址再给旧的结点
int ListInsert(LinkList &L,int i,ElemType e)
{
p=L;j=0;
while(p&&(j<i-1))
{p = p->next;j++}
if(!p||j>i-1)return ERROR;
s = new LNode;
s->data = e;
s->next = p->next;//a指向下一部分的指针要先给新给的结点。
p->next =s;//a指向下一部分的指针要先给新给的结点。
return OK;
}
2.5单链表的删除
这和单链表的插入差不多，但是要注意，除了修改结点a的指针域外，还要释放掉结点的数据域；所以这是需要一个新的q，临时保存要删除结点的地址以备释放。
步骤：
1>查找结点ai-1；
2>临时保存待删除结点ai的地址在q中，以备释放；
3>将结点*p的指针域指向ai的直接后继结点
4>释放结点ai的空间；
int ListDelete(LinkList &L,int L)
{
p=L;j=0;
while((p->next)&&(j<i+1))
{p = p->next;j++}
if(!(p->next)||(j>i-1)) return ERROR;
q = p - >next;
p->next = q->next;
delete q;
return OK;
}
2.6创建单链表
2.6.1前插法创建单链表
头插法：把后建立的结点插在头部。用这种方法建立起来的链表的实际顺序与输入顺序刚好向反，输出时为倒序！
1>创建一个只有头节点的空链表
2>输入n，循环n次执行以下操作
~ 生成一个新结点p
~ 输入元素赋值给p的数据域
~ 将新结点*插入到头节点之后
void CreatList(List &L,int n)
{
L=new LNode;
L->next=NULL;
for(int i=0;i<n;i++)
{
p=new LNode;
cin>>p->data;
p->next=L->next;
L->next=p;
}
}
2.6.2尾插法创建单链表：
将后建立的结点插在链表尾部，这种方法建立起来的链表的实际顺序与输入顺序相同，在对链表顺序有严格要求时，建议使用尾插法
void CreateList(List &L,int n)
{
L=new LNode;
L->next=NULL;
r=L;
for(i=0;i<n;++i)
{
p=new LNode;
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}node;
int L;
struct node *tailcreat()
{
struct node *p,*q,*head;
int n = 0;
head = (struct node*)malloc(sizeof(struct node));
p = (struct node*)malloc(sizeof(struct node));
printf("请输入数字，以0结尾:\n");
do{
q = (struct node*)malloc(sizeof(struct node));
scanf("%d",&q->data);L++;
if(q->data == 0)break;
if(n == 0)
{
head->next = q;
p->next = q;
p = q;
n++;
}
p->next = q;
p = q;
}while(true);
p->next = NULL;
return (head);
}
struct node *headcreat()
{
struct node *p,*q,*head;
head = (struct node*)malloc(sizeof(struct node));
p = (struct node*)malloc(sizeof(struct node));
p->next = NULL;
printf("请输入数字，以0结尾：\n");
do{
q = (struct node*)malloc(sizeof(struct node));
scanf("%d",&q->data);
if(q->data == 0)break;
L++;
q->next = p->next;
p->next = q;
}while(true);
head = p;
return (head);
}
struct node *insert(struct node *head)
{
struct node *r,*p;
int i,j;
p = head;
r = (struct node*)malloc(sizeof(struct node));
printf("请输入你要插入的位置:\n");
scanf("%d",&i);
printf("请输入你要插入的数字：\n");
scanf("%d",&r->data);
for(j=1;j<i;j++)
p = p->next;
r->next = p->next;
p->next = r;
L++;
return(head);
}
struct node *del(struct node *head)
{
struct node *p;
int i;
p = head;
printf("请输入你要删除的数字：\n");
scanf("%d",&i);
while(i!=(p->next)->data)
p = p->next;
p->next = (p->next)->next;
L--;
return(head);
}
void display(struct node *head)
{
while(head->next!=NULL)
{
printf("%d ",(head->next)->data);
head = head->next;
}
}
int main()
{
struct node *head;
head = tailcreat();
display(head);
head = insert(head);
display(head);
head = del(head);
display(head);
return 0;
}
上一篇： python_字符串
下一篇： 数据结构第二章C语言———线性表