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;
}