單鏈表操作
- [x] 單鏈表的創(chuàng)建（尾插法现横、頭插法）
- [x] 單鏈表的查找操作
- [x] 單鏈表的刪除操作
- [x] 單鏈表的逆置操作(使用頭插法)
- [x] 單鏈表表長的計算
- [x] 打印單鏈表
單鏈表的創(chuàng)建
頭插法
forward_list* creat_3() //頭插法
{
forward_list *head,*s;
int num;
head = NULL;//鏈表初始狀態(tài)為空
while(scanf("%d",&num) && num)
{
s = (forward_list*)malloc(sizeof(forward_list));
s->data = num;
s->next = head;
head = s;//將新結點插入到表頭
}
return head;
}
尾插法（不含頭結點）
//尾插法建表
forward_list* creat_1()
{
forward_list *head=NULL;//頭指針，初始狀態(tài)為空
forward_list *rear=NULL;//尾指針，初始狀態(tài)為空
int num;
forward_list *s;
while(scanf("%d",&num) == 1 && num)//輸入0結束
{
s = (forward_list*)malloc(sizeof(forward_list));
s->data = num;
if(head == NULL)//將新節(jié)點加入空表
head = s;
else //原表非空猛遍，將新節(jié)點鏈接到表尾之后
rear->next = s;
rear = s;//尾指針指向新的表尾
}
if(rear!= NULL)//對于非空表农曲，將尾結點的下一個結點置空
rear->next = NULL;
return head;
}
尾插法（含頭結點）
//尾插法建表,包含頭結點
forward_list* creat_2()
{
forward_list *s;
forward_list *head, *rear;
int num;
head = (forward_list*)malloc(sizeof(forward_list));
rear = head;
while(scanf("%d",&num)==1 && num)
{
s = (forward_list*)malloc(sizeof(forward_list));
s->data = num;
rear->next = s;
rear = s;//表指針指向新的表尾
}
rear->next = NULL;
return head;
}
單鏈表的查找操作
按值查找
void search_1(forward_list *s, int x)
{
forward_list *p;
p = s;
while(p != NULL)
{
if(p->data == x)
{
printf("\nthe value : %d is exist !\n",x);
return ;
}
p = p->next;
}
printf("\nthe value : %d is not fonud !\n",x);
}
按值查找（包含頭結點）
void search_2(forward_list *s, int x)//帶頭節(jié)點
{
forward_list *p;
p = s->next;//emmmm
while(p != NULL)
{
if(p->data == x)
{
printf("\nthe value : %d is exist !\n",x);
return ;
}
p = p->next;
}
printf("\nthe value : %d is not fonud !\n",x);
}
單鏈表的刪除操作
按給定結點的位置刪除（帶頭結點）
void delete_1(forward_list *head,int i) //刪除第i個節(jié)點(單鏈表包含頭節(jié)點)
{
int j=0;
forward_list *p,*q;
p=head;
j=0;
while((p->next!=NULL)&&(j<i-1))
{
p=p->next;
j++;
}
if(p->next!=NULL)
{
q=p->next;
p->next=p->next->next;
free(q);
}
else
printf("illegal delete position,delete failed!");
}
按照指定值刪除結點(不帶頭結點)
void forward_list_delete_1(forward_list *s,int x)//刪除鏈表（不帶頭節(jié)點）中指定值的元素
{
forward_list *p;
forward_list *temp;//用來存放被刪除元素的前一個結點
p = s;
if(x == p->data)
free(p);
temp = p;
p = p->next;
while(p != NULL)
{
if(p->data == x)
{
temp->next = p->next;
free(p);
return ;
}
temp = p;
p = p->next;
}
printf("\n你要刪除的元素 %d 不在表中\(zhòng)n",x);
return ;
}
單鏈表的逆置
頭插法逆置(帶頭結點)
void reverse_2(forward_list *head)//頭插法逆置,帶頭節(jié)點
{
forward_list *p,*q;
p=head->next;
head->next=NULL;
while(p)
{
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
}
計算單鏈表的表長
*** 帶頭結點 ***
void list_length_2(forward_list *s)
{
int count;
forward_list *p=s->next;
while(p)
{
count++;
p = p->next;
}
printf("\nlist length: %d\n",count);
}
*** 不帶頭結點 ***
void list_length_1(forward_list *s)
{
int count;
forward_list *p=s;
while(p)
{
count++;
p = p->next;
}
printf("\nlist length: %d\n",count);
}
打印單鏈表
*** 帶頭結點 ***
void print_forward_list_2(forward_list *s)//打印含頭節(jié)點的單鏈表
{
forward_list *p;
p = s->next;//因為含有頭節(jié)點贺拣，head->data的數據域的數據未知
while(p != NULL)
{
printf("%-3d",p->data);
p = p->next;
}
return ;
}
*** 不帶頭結點 ***
void print_forward_list_1(forward_list *s)//打印單鏈表
{
forward_list *p;
p = s;
while(p != NULL)
{
printf("%4d",p->data);
p = p->next;
}
return ;
}
試試
源程序
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//定義單鏈表結點類型
typedef struct node{
int data; //結點數據域
struct node *next; //結點指針域
}forward_list;
//尾插法建表
forward_list* creat_1()
{
forward_list *head=NULL;//頭指針，初始狀態(tài)為空
forward_list *rear=NULL;//尾指針根吁，初始狀態(tài)為空
int num;
forward_list *s;
while(scanf("%d",&num) == 1 && num)//輸入0結束
{
s = (forward_list*)malloc(sizeof(forward_list));
s->data = num;
if(head == NULL)//將新節(jié)點加入空表
head = s;
else //原表非空，將新節(jié)點鏈接到表尾之后
rear->next = s;
rear = s;//尾指針指向新的表尾
}
if(rear!= NULL)//對于非空表合蔽，將尾結點的下一個結點置空
rear->next = NULL;
return head;
}
//尾插法建表,包含頭結點
forward_list* creat_2()
{
forward_list *s;
forward_list *head, *rear;
int num;
head = (forward_list*)malloc(sizeof(forward_list));
rear = head;
while(scanf("%d",&num)==1 && num)
{
s = (forward_list*)malloc(sizeof(forward_list));
s->data = num;
rear->next = s;
rear = s;//表指針指向新的表尾
}
rear->next = NULL;
return head;
}
forward_list* creat_3() //頭插法
{
forward_list *head,*s;
int num;
head = NULL;//鏈表初始狀態(tài)為空
while(scanf("%d",&num) && num)
{
s = (forward_list*)malloc(sizeof(forward_list));
s->data = num;
s->next = head;
head = s;//將新結點插入到表頭
}
return head;
}
void search_1(forward_list *s, int x)
{
forward_list *p;
p = s;
while(p != NULL)
{
if(p->data == x)
{
printf("\nthe value : %d is exist !\n",x);
return ;
}
p = p->next;
}
printf("\nthe value : %d is not fonud !\n",x);
}
void search_2(forward_list *s, int x)//帶頭節(jié)點
{
forward_list *p;
p = s->next;//emmmm
while(p != NULL)
{
if(p->data == x)
{
printf("\nthe value : %d is exist !\n",x);
return ;
}
p = p->next;
}
printf("\nthe value : %d is not fonud !\n",x);
}
void reverse_1(forward_list *head)//頭插法逆置單鏈表
{
forward_list *p;
forward_list *temp;
p = head;//存好之前的單鏈表
//printf("\n%d\n",p->data);
head->next = NULL;
while(p)
{
temp = p;
//printf("1");
p = p->next;
temp->next = head->next;
head = temp;
printf("\n%d\n",head->data);
}
}
void reverse_2(forward_list *head)//頭插法逆置,帶頭節(jié)點
{
forward_list *p,*q;
p=head->next;
head->next=NULL;
while(p)
{
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
}
void forward_list_delete_1(forward_list *s,int x)//刪除鏈表（不帶頭節(jié)點）中指定值的元素
{
forward_list *p;
forward_list *temp;//用來存放被刪除元素的前一個結點
p = s;
if(x == p->data)
free(p);
temp = p;
p = p->next;
while(p != NULL)
{
if(p->data == x)
{
temp->next = p->next;
free(p);
return ;
}
temp = p;
p = p->next;
}
printf("\n你要刪除的元素 %d 不在表中\(zhòng)n",x);
return ;
}
void delete_1(forward_list *head,int i) //刪除第i個節(jié)點(單鏈表包含頭節(jié)點)
{
int j=0;
forward_list *p,*q;
p=head;
j=0;
while((p->next!=NULL)&&(j<i-1))
{
p=p->next;
j++;
}
if(p->next!=NULL)
{
q=p->next;
p->next=p->next->next;
free(q);
}
else
printf("illegal delete position,delete failed!");
}
/*//不對
void list_delete(forward_list *s, int i)//刪除單鏈表(不帶頭節(jié)點)的第i個結點
{
int count=1;
forward_list *p,*q;
p=s;
//將p移動到被刪除結點的前一個結點
while((p!=NULL)&&(count<i-1))
{
p=p->next;
count++;
}
if(i == count)
{
q = p;
p = p->next;
free(q);
return ;
}
if(p->next!=NULL)
{
q=p->next;
p->next=p->next->next;
free(q);
}
else
printf("illegal delete position,delete failed!");
}
*/
void list_length_1(forward_list *s)
{
int count;
forward_list *p=s;
while(p)
{
count++;
p = p->next;
}
printf("\nlist length: %d\n",count);
}
void list_length_2(forward_list *s)
{
int count;
forward_list *p=s->next;
while(p)
{
count++;
p = p->next;
}
printf("\nlist length: %d\n",count);
}
void print_forward_list_1(forward_list *s)//打印單鏈表
{
forward_list *p;
p = s;
while(p != NULL)
{
printf("%4d",p->data);
p = p->next;
}
return ;
}
void print_forward_list_2(forward_list *s)//打印含頭節(jié)點的單鏈表
{
forward_list *p;
p = s->next;//因為含有頭節(jié)點击敌，head->data的數據域的數據未知
while(p != NULL)
{
printf("%-3d",p->data);
p = p->next;
}
return ;
}
int main()
{
/*不帶頭結點的單鏈表*/
printf("使用不帶頭結點的單鏈表:\n");
forward_list *p;
printf("尾插法建表:\n");
p = creat_1();//尾插法建表
print_forward_list_1(p);
list_length_1(p);
//查找是否存在值為6的結點
search_1(p,6);
printf("\n刪了個5后，表變?yōu)閈n");
forward_list_delete_1(p,5);
print_forward_list_1(p);
//頭插法建表
forward_list *s;
printf("\n頭插法建表:\n");
s = creat_3();
print_forward_list_1(s);
list_length_1(s);
/*帶頭結點的單鏈表*/
printf("\n\n使用帶頭結點的單鏈表:\n");
forward_list *t;
t = creat_2();
print_forward_list_2(t);
search_2(t,6);
list_length_2(t);
printf("\n逆置:\n");
reverse_2(t);
print_forward_list_2(t);
list_length_2(t);
return 0;
}
運行結果
image
