c语言单链表操作

㈠ c语言的单链表问题，谢谢解答

单链表简介
链表中的数据是以结点来表示的，每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表
以"结点的序列"表示线性表称作线性链表(单链表)

单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。

因此，查找第 i 个数据元素的基本操作为:移动指针，比较 j 和 i

单链表

1、链接存储方法

链接方式存储的线性表简称为链表(Linked List)。

链表的具体存储表示为:

① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的，也可以是不连续的)

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))

注意:

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

2、链表的结点结构

┌───┬───┐

│data │next │

└───┴───┘

data域--存放结点值的数据域

next域--存放结点的直接后继的地址(位置)的指针域(链域)

注意:

①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。

②每个结点只有一个链域的链表称为单链表(Single Linked List)。

【例】线性表(bat，cat，eat，fat，hat，jat，lat，mat)的单链表示如示意图

3、头指针head和终端结点指针域的表示

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。

注意:

链表由头指针唯一确定，单链表可以用头指针的名字来命名。

终端结点无后继，故终端结点的指针域为空，即NULL。

4、单链表的一般图示法

由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表(bat，cat，fat，hat，jat，lat，mat)的单链表就可以表示为下图形式。

5、单链表类型描述

typedef char DataType; //假设结点的数据域类型为字符

typedef struct node{ //结点类型定义

DataType data; //结点的数据域

struct node *next;//结点的指针域

}ListNode;

typedef ListNode *LinkList;

ListNode *p;

LinkList head;

注意:

①LinkList和ListNode是不同名字的同一个指针类型(命名的不同是为了概念上更明确)

②*LinkList类型的指针变量head表示它是单链表的头指针

③ListNode类型的指针变量p表示它是指向某一结点的指针

6、指针变量和结点变量

指针变量
结点变量
定义
在变量说明部分显式定义
在程序执行时，通过标准函数malloc生成
取值
非空时，存放某类型结点
实际存放结点各域内容的地址
①生成结点变量的标准函数

p=( ListNode *)malloc(sizeof(ListNode));

//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中

②释放结点变量空间的标准函数

free(p);//释放p所指的结点变量空间

③结点分量的访问

利用结点变量的名字*p访问结点分量

方法一:(*p).data和(*p).next

方法二:p->data和p->next

④指针变量p和结点变量*p的关系

指针变量p的值--结点地址

结点变量*p的值--结点内容

(*p).data的值--p指针所指结点的data域的值

(*p).next的值--*p后继结点的地址

*((*p).next)--*p后继结点

注意:

① 若指针变量p的值为空(NULL)，则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。

② 有关指针类型的意义和说明方式的详细解释

可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。

因此，在单链表中第 i 个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

㈡ 编写一个C语言程序 实现单链表的基本操作

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef struct Node
{
int data;
struct Node * pNext;
} * PNODE, NODE;

PNODE establish_list (void);
void traverse_list (PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
void sort_list(PNODE pHead);
void insert_list(PNODE pHead, int pos, int val);
int delete_list(PNODE pHead, int pos, int val);
void freeer(PNODE pHead);

int main(void)
{
PNODE pHead;
int len, i, j, val;
pHead = establish_list();
traverse_list(pHead);

if(is_empty(pHead))
printf("链表为空\n");
else
printf("链表不空\n");

len = length_list(pHead);
printf("链表的长度为: %d\n", len);

sort_list(pHead);
traverse_list(pHead);

printf("请输入您要在第几个节点插入\n");
scanf("%d", &i);
printf("请输入您要在第%d个节点插入的值\n", i);
scanf("%d", &j);
insert_list(pHead, i, j);
traverse_list(pHead);
printf("请输入您要第几个删除的节点\n");
scanf("%d", &i);
val = delete_list(pHead, i, val);
printf("您删除的节点值为: %d\n", val);
traverse_list(pHead);
freeer(pHead);

return 0;
}

PNODE establish_list(void)//初始化链表，返回头结点地址
{
int val, len;
PNODE Tem;
PNODE pNew;
PNODE pHead;

pHead = (PNODE)malloc(sizeof(NODE));
Tem = pHead;
if(NULL == pHead)
{
printf("分配失败");
exit(-1);
}
Tem->pNext = NULL;
printf("请输入您要定义节点的长度: ");
scanf("%d", &len);

for (int i=0;i<len;++i)
{
printf("请输入第%d个节点的值: ", i+1);
scanf("%d", &val);

pNew = (PNODE)malloc(sizeof(NODE));

if(NULL == pNew)
{
printf("分配失败");
exit(-1);
}
pNew->data = val;//首先把本次创建的新节点的值付给新节点的数据域
Tem->pNext = pNew;//然后使用临时的节点变量的指针域保存了新节点的地址，也就是指向了新节点
pNew->pNext = NULL;//如何再不循环，新节点成为最后一个节点
Tem = pNew;//把本次分配的新节点完全的赋给Tem，Tem就成为了这次新节点的影子,那么下次分配新节点时可以使用上个新节点的数据
}
return pHead;
}

void traverse_list(PNODE pHead)
{
PNODE p = pHead;//使用P是为了不改写头结点里保存的地址
p = pHead->pNext;//使P指向首节点

while(p != NULL)//P本来就是头结点的指针域，也就是首节点的地址，既然是地址就可以直接判断p是否等于NULL
{
printf("%d ", p->data);
p = p->pNext;//使P每循环一次就变成P的下一个节点
}
}

bool is_empty(PNODE pHead)
{
if(NULL == pHead->pNext)
return true;
else
return false;
}

int length_list(PNODE pHead)
{
PNODE p = pHead->pNext;
int len = 0;

while(p != NULL)
{
len++;
p = p->pNext;
}
return len;
}

void sort_list(PNODE pHead)
{
int i, j, t, len;
PNODE p, q;
len = length_list(pHead);

for(i=0,p=pHead->pNext;i<len;i++,p=p->pNext)//逗号后只是为了找到下一个节点，因为不是数组，所以不能使用下标来++
{
for(j=0,q=pHead->pNext;j<len;j++,q=q->pNext)
if(q->data > p->data)//这里的大小与号可以决定是升序还是降序，如果是大于号就是升序,反之小于号就是降序
{
t = q->data;
q->data = p->data;
p->data = t;
}
}

return;
}

void insert_list(PNODE pHead, int pos, int val)
{
int i;
PNODE q = pHead;
PNODE p = pHead;
if(pos > 0 && pos <= length_list(pHead))
{
for(i=0;i<pos;i++)
{
q = q->pNext;//q就是要插入的连接点
}
for(i=1;i<pos;i++)
{
p = p->pNext;//p就是要插入连接点的前一个节点
}
PNODE pNew = (PNODE)malloc(sizeof(NODE));
p->pNext = pNew;
pNew->data = val;
pNew->pNext = q;
}
else if(pos > length_list(pHead))//追加
{
PNODE t;
t = pHead;
PNODE PN;
PN = (PNODE)malloc(sizeof(NODE));
if(PN == NULL)
printf("分配失败");
else
while(t->pNext != NULL)
{
t = t->pNext;//使T->pNext成为尾结点
}
PN->data = val;//给新节点赋予有效数据
t->pNext = PN;//使尾结点的指针域指向了新的结点
PN->pNext = NULL;//新节点成为尾结点
}
else
printf("error\n");
return;
}

int delete_list(PNODE pHead, int pos, int val)
{
int i, j;
PNODE q, p;
q = pHead;
p = pHead;

if(pos > 0 && pos <= length_list(pHead))//保证删除的是节点的有效数
{
for(i=0;i<pos;i++)
{
p = p->pNext;
}
for(j=1;j<pos;j++)
{
if(pos == 0)
q = pHead;
else
q = q->pNext;
}
q->pNext = p->pNext;
val = p->data;

free(p);
return val;
}
else
printf("error");

}

void freeer(PNODE pHead)
{
PNODE pT = pHead;
while(NULL != pHead->pNext)
{
free(pT);
pT = pT->pNext;
}

return;
}
/*
好久以前写的一个链表了，有排序，插入，删除，输出，判断是否为空，甚至还有释放堆中内存的功能
*/

㈢ 用C语言编程实现单链表的基本操作

第二个显示为什么?为什么什么东西都没有、
#include<stdio.h>
typedef
struct
sample
{
char
ch;
struct
sample
*next;
}LNode;
LNode
*Createlist(LNode
*head)
//创建单链表,头插入法
{
LNode
*p;
if((head=(LNode
*)malloc(sizeof(LNode)))==NULL)
printf("aply
error\n");
head->next=NULL;
head->ch
=
'\0';
int
i=
0;
printf("请一次输入A-Z:\n");
for(i
=
0
;
i
<
26;
++i)
{
p=(LNode
*)malloc(sizeof(LNode));
if(!p)
printf("aply
error\n");
scanf("%c",&p->ch);
p->next
=
head->next;
head->next=p;
}
return
head;
}
LNode
*EncryptList(LNode*
head)
{
LNode
*p=
head,*q
=
head->next,*r
=
head->next;
while(p->next)
{
p
=
p->next;
}
int
i
=
0
;
for(i
=
0
;
i
<
3;
i++)
{
p->next
=
r;
p
=
p->next;
q
=
q->next;
r
=
q;
}
p->next
=NULL;
head->next
=
q;
return
head;
}
void
ListPrint(LNode
*head)
{
LNode
*p
=
head->next;
while(p->next!=NULL)
{
printf("%c\t",p->ch);
p=p->next;
}
printf("%c\n",p->ch);
}
int
main(void)
{
LNode
*head;
head
=
Createlist(head);//链表初始化
ListPrint(head);
//打印单链表数据
head
=
EncryptList(head);
ListPrint(head);
return
0;
}
看看。

㈣ c语言数据结构单链表（头插入法）

head=(LNode
*)malloc(sizeof(LNode));
这一句不要，没啥用处，除非你head指向的节点也就是第一个节点的data不需要数据
head->next=NULL;这里修改为head=NULL;
让head先指向NULL，也就是没有节点
其实这个可以不要，再主函数中，先让链表是空链表即可（即让head=NULL）
head->data=data;
head->next=p->next;
head->next=p;
关键在这里
你仔细考虑一下，一般来说头插法的head只是一个指针，不要对head指向的那个节点操作，对p操作完成后，让head指过去即可
所以修改为
p->data=data;
//赋值过去，因为你现在申请了p的内存空间
p->next=head;
//把head指向的那个节点连接到p的后面，这样完成头插
//
这是head没有用了，p成为链表的头指针
head=p;
//head再指向这个链表的头部，也就是p指向的节点，为下一次循环做准备
head=Createlist(head);//链表初始化
主函数中这样不太好，建议不要重名

㈤ 用C语言实现对单链表的基本操作

#include<stdio.h>
#include<stdlib.h>

typedefintDataType;

typedefstructnode{
	DataTypemember;
	structnode*next;
}*LinkList,*pNode;

//初始化链表
LinkListGetEmptyList(){
	LinkListhead=(pNode)malloc(sizeof(structnode));
	head->member=0;
	head->next=NULL;
	returnhead;
}


//在非增链表中插入结点
voidInsertNode(LinkListhead,DataTypex){
	pNodep,q;
	for(p=head;p->next!=NULL;p=p->next){
		if(p->next->member<=x){
			q=(pNode)malloc(sizeof(structnode));
			q->member=x;
			q->next=p->next;
			p->next=q;
			return;
		}
	}
	q=(pNode)malloc(sizeof(structnode));
	q->member=x;
	q->next=p->next;
	p->next=q;
}

//新结点插入为首结点
voidPushNode(LinkListhead,DataTypex){
	pNodep=(pNode)malloc(sizeof(structnode));
	p->member=x;
	p->next=head->next;
	head->next=p;
}

//删除结点
intDeleteNode(LinkListhead,DataTypex){
	pNodep,q;
	for(p=head;p!=NULL;p=p->next){
		if(p->next->member==x){
			q=p->next;
			p->next=q->next;
			free(q);
			return1;//成功删除member(第一个)为x的结点
		}
	}
	return0;//没有找到member为x的结点
}

//查找结点
intFindNode(LinkListhead,DataTypex){
	pNodep;
	for(p=head->next;p!=NULL;p=p->next){
		if(p->member==x)return1;//找到了
	}
	return0;//没有找到
}

//销毁链表
voidDestroyList(LinkListhead){
	pNodeq,p=head;
	while(p){
		q=p;
		p=q->next;
		free(q);
	}
	head=NULL;
}

//遍历链表
voidShowList(LinkListhead){
	pNodep=head->next;
	while(p!=NULL){
		printf("%d",p->member);
		p=p->next;
	}
	printf("
");
}

intmain(){
	DataTypex,res;
	LinkListhead=GetEmptyList();
	printf("输入一个整数('q'toquit):");
	while(scanf("%d",&x)==1){
		InsertNode(head,x);//创建非增链表
		printf("输入一个整数('q'toquit):");
	}
	fflush(stdin);
	ShowList(head);
	printf("输入待查找的整数:");
	scanf("%d",&x);
	res=FindNode(head,x);
	if(res)printf("找到了。
");
	elseprintf("没找到！
");
	printf("输入待删除的整数:");
	scanf("%d",&x);
	res=DeleteNode(head,x);
	if(res)printf("成功删除。
");
	elseprintf("没找到数据为:%d的结点！
",x);
	ShowList(head);
	DestroyList(head);
	return0;
}