数据结构使用二级指针创建单链表以及单链表的各种操作
//单链表创建
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define flag -1
//创建节点
typedef struct Node{
int data;
struct Node *next;
} LNode,*listNode;
void showMenu(){
printf("\t\t\t\t\t\t1.使用头插法创建链表\n");
printf("\t\t\t\t\t\t2.使用尾插法创建链表\n");
printf("\t\t\t\t\t\t3.按序号查找\n");
printf("\t\t\t\t\t\t4.按值查找\n");
printf("\t\t\t\t\t\t5.按值插入\n");
printf("\t\t\t\t\t\t6.按位置插入\n");
printf("\t\t\t\t\t\t7.删除链表\n");
printf("\t\t\t\t\t\t8.测试链表并获得长度\n");
printf("\t\t\t\t\t\t9.将单链表倒置\n");
}
//测试链表并获得长度
int testList(listNode L){
printf("测试结果:\n");
int length = 0;
LNode *temp = NULL;
temp = L;
if(temp == NULL){
printf("temp is NULL!\n");
}
while(temp!=NULL){
printf("%d ",temp->data);
temp = temp->next;
length++;
}
printf("\n链表的长度：%d",length);
return length;
}
//头插法创建单链表
void creatListNodeOfHead(listNode * L){ //注意有时指针不一定是传地址
LNode *head;//head只是暂时指向申请的空间
int input;
(*L) = NULL;
printf("传递的指针参数%p\n",L);
printf("指针内容%p\n",(*L));
printf("请输入(以-1为结束标志!)：\n");
scanf("%d",&input);
while(input != flag){
head = (listNode)malloc(sizeof(LNode));
head->data = input;
head->next = (*L);
*L = head;
//printf("head创建完成\n");
scanf("%d",&input);
//printf("%d",(*L)->data);
}
}
//尾插法创建单链表
void creatListNodeOfEnd(listNode * L){ //必须有一个头节点
listNode tail = *L,head = NULL; //注意这里的指针赋值是值传递
int input;
head = (listNode)malloc(sizeof(LNode));
*L = head;
printf("*L的值：%p\n",*L);
printf("tail的值：%p\n",tail);
tail = head;
printf("请输入:(以-1为结束标志!)\n");
scanf("%d",&input);
while(input != flag){
head->data = input;
(tail)->next = head;
(tail) = head;
head = (listNode)malloc(sizeof(LNode));
scanf("%d",&input);
}
tail->next = NULL;
printf("*L的内容：%p\n",*L);
}
//按序号查找
listNode locatonListBySerialNumber(listNode L,int length){
int i =1;
int num;
printf("\n请输入序号：");
scanf("%d",&num);
if(num > length)
printf("链表长度不够！\n");
while(L != NULL && i != num){
L = L->next;
i++;
}
if(L == NULL){
L = NULL;
}
return L;
}
//按值查找
listNode locatonListByValue(listNode L){
int num;
printf("\n请输入数值：");
scanf("%d",&num);
while(L != NULL && L->data != num){
L = L->next;
}
if(L == NULL){
L = NULL;
}
return L;
}
//按值插入
int insertListNodeByValue(listNode L){
int num;
int result;
listNode input = (listNode)malloc(sizeof(LNode));
printf("请输入插入位置的前一个数的值：");
scanf("%d",&num);
printf("\n请输入要插入的值：");
scanf("%d",&(input->data));
while(L != NULL && L->data != num){
L = L->next;
}
if(L == NULL){
printf("插入失败！请检查输入的值是否正确！\n");
result = -1;
}
else{
input->next = L->next;
L->next = input;
result = 1;
}
return result;
}
//按位置插入
int insertListNodeByPosition(listNode L){
int num,i = 1;
int result,length;
listNode input = (listNode)malloc(sizeof(LNode));
printf("请输入插入位置的前一个位置：");
scanf("%d",&num);
length = testList(L);
if(length <= 0){
printf("链表长度为0！\n");
return -1;
}
if(num > length+1 || num < 0){
printf("输入的数值不合适！\n");
return -1;
}
printf("\n请输入要插入的值：");
scanf("%d",&(input->data));
while(L != NULL && i != num){
L = L->next;
i++;
}
if(L == NULL){
printf("插入失败！请检查输入的值是否正确！\n");
result = -1;
}
else{
input->next = L->next;
L->next = input;
result = 1;
}
return result;
}
//定点删除
int deleteByPosition(listNode L,int position){
printf("按内容删除！\n");
int result=0;
listNode p;
while(L != NULL && L->data != position){
p = L;
L = L->next;
}
if(L != NULL){
p->next = L->next;
free(L);
result = 1;
}
return result;
}
//全部删除
int deleteAll(listNode L){
listNode p;
int result = 0;
while(L != NULL){
p = L;
L = L->next;
free(p);
testList(L);
printf("删除过程演示,按任意键继续....\n");
getch();
}
if(L == NULL)
result = 1;
return result;
}
//反转单链表
int reserveList(listNode L){
listNode p,q;
int result = 0;
p = L;
L = NULL;
while(p){
q = p;
p = p->next;
q->next = L;
L = q;
}
if(p == NULL ){
result = 1;
}
return result;
}
int main(){
LNode *L =NULL;
int length = 0;
printf("原指针地址%p\n",&L);
printf("原指针内容%p\n",L);
//查找运算结果
listNode resultOfFind = NULL;
//插入结果
int resultOfInsert = NULL;
int choose;
while(1){
showMenu();
printf("请选择操作序号：\n");
scanf("%d",&choose);
switch(choose){
case 1:
//使用头插法
creatListNodeOfHead(&L);
printf("创建成功按任意键返回主菜单\n");
getch();
break;
case 2:
//使用尾插法
creatListNodeOfEnd(&L);
printf("创建成功按任意键返回主菜单\n");
getch();
break;
case 3:
if(L == NULL ){
printf("没有链表！请先创建链表！\n");
break;
}
//按序号查找
resultOfFind = locatonListBySerialNumber(L,length);
if(resultOfFind == NULL){
printf("未查到相应的值！\n");
}
else{
printf("查找成功！结果是：%d",resultOfFind->data);
}
printf("按任意键返回主菜单\n");
getch();
break;
case 4:
if(L == NULL ){
printf("没有链表！请先创建链表！\n");
break;
}
//按值查找
resultOfFind = locatonListByValue(L);
if(resultOfFind == NULL){
printf("未查到相应的值！\n");
}
else{
printf("查找成功！结果是：%d",resultOfFind->data);
}
printf("按任意键返回主菜单\n");
getch();
break;
case 5:
if(L == NULL ){
printf("没有链表！请先创建链表！\n");
break;
}
//插入操作按值插入
resultOfInsert = insertListNodeByValue(L);
if(resultOfInsert == 1)
printf("插入成功!按任意键返回主菜单\n");
getch();
break;
case 6:
if(L == NULL ){
printf("没有链表！请先创建链表！\n");
break;
}
//插入操作按位置插入
resultOfInsert = insertListNodeByPosition(L);
if(resultOfInsert == 1)
printf("插入成功!按任意键返回主菜单\n");
getch();
break;
case 7:
if(L == NULL ){
printf("没有链表！请先创建链表！\n");
break;
}
int chooseOfDelete;
//释放申请的内存
printf("删除指定链表请按1;全部删除请按2:\n");
scanf("%d",&chooseOfDelete);
switch(chooseOfDelete){
case 1:
printf("请输入要删除的节点的值：\n");
int position; //奇怪 要是变量声明放在printf前面则报错。
scanf("%d",&position);
if(deleteByPosition(L,position) == 1){
printf("删除成功！按任意键按继续操作....\n");
getch();
}
else{
printf("删除失败！按任意键按继续操作....\n");
getch();
}
break;
case 2:
if(deleteAll(L) == 1){
printf("全部删除！按任意键按返回操作菜单！\n");
getch();
}
else{
printf("删除失败！按任意键按返回操作菜单！\n");
getch();
}
break;
}
break;
case 8:
if(L == NULL ){
printf("没有链表！请先创建链表！按任意键返回主菜单\n");
getch();
break;
}
length = testList(L);
printf("\n测试结束！返回菜单请按任意键！\n");
getch();
break;
case 9:
if(L == NULL){
printf("没有链表！请先创建链表！按任意键返回主菜单\n");
getch();
break;
}
if(reserveList(L)){
///有bug！！！！！！！
printf("链表反转成功！\n");
testList(L);
printf("\n测试结束！返回菜单请按任意键！\n");
getch();
}
}
system("cls");
}
return 0;
}
