資料結構之單連結清單的簡單操作（插入 删除 查找 撤銷 列印）

連結表首先要建立指針域和資料域，并用本節點的指針域指向下一個節點，對于連結清單的特點這裡不做詳細解釋

1.建立指針域和資料域

typedef struct Noded{
	struct Noded *next;//指針域 
	int data;//資料域 
}Noded; 
           

2.對連結清單進行初始化，連結清單為空（確定建立空連結清單）

//連結清單初始化 
void Init(Noded *head){
	head->next = NULL;
}
           

3.實作連結清單的各種操作

插入：采用頭插法：連結清單為空時，head指向NULL；連結清單不為空時，head指向第一個節點，插入時，p的next指向head的next，head的next指向p。

//頭插法建立連結清單 
void headInsert(Noded *head,int x){
	Noded *p;
	p = (struct Noded*)malloc(sizeof(struct Noded));
	p->data = x;
	p->next = head->next;
	head->next = p;
	
} 
           

得到連結清單的長度，對連結清單進行周遊即可

//得到連結清單長度 
int getLen(Noded *head){
	Noded *cur = head->next;
	int count=0;
	while(cur != NULL){
		count++;
		cur = cur->next;
	}
	return count;
} 
           

插入：在下标 k 的位置插入，移動連結清單指針到 k 的位置，進行插入

//在下标為k的位置插入元素 x 
void insert(Noded *head, int k, int x){
	Noded *cur,*p;
	int i;
	p = (struct Noded*)malloc(sizeof(struct Noded));
	p->data = x;
	cur = head;
	for(i = 0; i < k; i++) {
		cur = cur->next;
	}
	p->next = cur->next;
	cur->next = p;
	
}
           

删除：删除下标為 k 的元素，先周遊到 k 位置，再删除即可

//删除下标為 k 的元素 
void dele(Noded *head,int k){
	Noded *cur = head;
	int i;
	for(i = 0; i < k; i++){
		cur = cur->next;
	}
	cur->next = cur->next->next;
	
} 
           

查找：查找元素值為 x 的節點，并傳回其下标 ，直接從第一個節點開始周遊，知道找到值為 x 的元素，記錄此時已經周遊的元素個數，傳回即可。如果連結清單不存在此元素，則傳回-1。

//查找元素值為 x 的節點，并傳回其下标 
int search(Noded *head,int x){
	Noded *cur = head->next;
	int i = 0;
	while(cur!=NULL){
		if(x == cur->data)
		return i;
		i++;
		cur = cur->next;
	} 
	return -1;
}
           

列印

//列印連結清單 
void print(Noded *head){
	if(head==NULL)
	return;
	Noded *cur = head->next;
	while(cur!=NULL){
		printf("%d ",cur->data);
		cur = cur->next;
	}
}
           

撤銷連結清單

//撤銷連結清單 
void destory(Noded *head){
	Noded *cur = head->next;
	while(cur!=NULL){
		free(cur);
		cur = cur->next;
	}
}

           

完整代碼如下

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

typedef struct Noded{
	struct Noded *next;//指針域 
	int data;//資料域 
}Noded; 

//連結清單初始化 
void Init(Noded *head){
	head->next = NULL;
}

//頭插法建立連結清單 
void headInsert(Noded *head,int x){
	Noded *p;
	p = (struct Noded*)malloc(sizeof(struct Noded));
	p->data = x;
	p->next = head->next;
	head->next = p;
	
} 

//得到連結清單長度 
int getLen(Noded *head){
	Noded *cur = head->next;
	int count=0;
	while(cur != NULL){
		count++;
		cur = cur->next;
	}
	return count;
} 

//在下标為k的位置插入元素 x 
void insert(Noded *head, int k, int x){
	Noded *cur,*p;
	int i;
	p = (struct Noded*)malloc(sizeof(struct Noded));
	p->data = x;
	cur = head;
	for(i = 0; i < k; i++) {
		cur = cur->next;
	}
	p->next = cur->next;
	cur->next = p;
	
}
//列印連結清單 
void print(Noded *head){
	if(head==NULL)
	return;
	Noded *cur = head->next;
	while(cur!=NULL){
		printf("%d ",cur->data);
		cur = cur->next;
	}
}

//删除下标為 k 的元素 
void dele(Noded *head,int k){
	Noded *cur = head;
	int i;
	for(i = 0; i < k; i++){
		cur = cur->next;
	}
	cur->next = cur->next->next;
	
} 

//查找元素值為 x 的節點，并傳回其下标 
int search(Noded *head,int x){
	Noded *cur = head->next;
	int i = 0;
	while(cur!=NULL){
		if(x == cur->data)
		return i;
		i++;
		cur = cur->next;
	} 
	return -1;
}

//撤銷連結清單 
void destory(Noded *head){
	Noded *cur = head->next;
	while(cur!=NULL){
		free(cur);
		cur = cur->next;
	}
}

int main(int argc, char *argv[]) {
	Noded *node, *node1;
	Init(node);       
	int i;
	for(i = 0; i < 7; i++){
		headInsert(node,i);
		//tailInsert(node,i);
	}
	
	print(node);
	printf("\n");
	insert(node,5,9);
	print(node);
	//print(node);
	printf("\n%d\n",getLen(node));
	printf("%d\n",search(node,9));
	dele(node,5);
	print(node);
	
	
}