// List1.cpp : Defines the entry point for the console application.
//
/*
C语言下的升序链表的基本操作 List1.cpp
-------------------------------------
作者： Software Engineering @ HIT
1093710210 Alex
时间： 2010.9.10
-------------------------------------
*/
//黄虎杰院长在数据结构基础与算法课上留的一个小练习。。。好几天了，一直没写，感觉不会太难，没想到一写还真是把自己整的挺蒙的，还要多练啊
//不过写链表的过程中学到了很多经验。。不要迷信网络。。感觉好乱。。还是准备一张白纸一支笔。。自己画得明白= =
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
struct List
{
int data;
struct List *next;
};
void menu();
struct List *Create(struct List *h) ; //创建和插入升序链表
void Display(struct List *h); //输出链表信息
struct List *Delete_all(struct List *h); //删除整个链表
struct List *Delete(struct List *h , int xdata) ; //删除链表中结点
struct List *Search(struct List *h , int xdata) ; //查找某节点位置，本例中返回了其地址
struct List *Revers(struct List *h) ; //实现链表的逆序
int main(int argc, char* argv[])
{
int choice,i =0;
struct List *position,*MyList = NULL;
int xdata;
menu();
while (1)
{
printf("请输入操作： ");
scanf("%d",&choice);
switch (choice)
{
case 1:
printf("Please input the node: /n");
MyList = Create( MyList);
break;
case 2:
printf("Please input the node you want to delete: /n");
scanf("%d",&xdata);
MyList = Delete( MyList,xdata);
break;
case 3:
printf("Please input the node you want to locate: /n");
scanf("%d",&xdata);
position = Search(MyList,xdata);
printf("the node position is %d",position);
break;
case 4:
Display(MyList);
break;
case 5:
MyList = Revers( MyList);
printf("The links reversed is :/n");
Display(MyList);
break;
case 6:
MyList = Delete_all(MyList);
printf("Link deleted ! /n");
break;
default:
printf("wrong!");
}
}
return 0;
}
void menu()
{
printf("单向升序链表的操作/n");
printf("-----------------------------------------/n");
printf("1 -> 创建升序链表链表或插入节点升序链表中/n");
printf("2 -> 删除链表中的某个节点/n");
printf("3 -> 返回某个节点的地址指针/n");
printf("4 -> 输出线性链表/n");
printf("5 -> 实现单向链表逆序/n");
printf("6 -> 删除整个线性表/n");
}
/*
函数功能：升序输入链表函数
函数参数：结构体指针
返回值 ： 结构体指针
*/
struct List *Create(struct List *h)
{
struct List *newpr = NULL;
struct List *temp = h;
struct List *flag = NULL;
int data;
newpr = (struct List *)malloc(sizeof (struct List));
if (newpr == NULL) //用于检查是否申请动态空间成功
{
printf("memory error");
exit(0);
}
scanf("%d",&data);
newpr->data = data;
newpr->next = NULL;
if (h == NULL)
h = newpr;
else
{
while (temp->next != NULL && temp->data <= data ) //老师上课用的<，我感觉还是应该用<=这样可以解决重复输入相同data无效的问题
{
flag = temp; //flag用于记录合适的插入点前的位置
temp = temp->next;
}
if (temp->data >data) //用于检查时否在两个值之间，可以看出是否到了链表的末尾
{
if (temp == h) //说明在表头前插入数据，产生新的表头
{
newpr->next = h ;
h = newpr ;
}
else
{
temp = flag; //把当前的位置前移一下，移到插入点前面
newpr->next = temp->next;
temp->next = newpr;
}
}
else //在表末插入
{
temp->next =newpr;
}
}
return h;
}
/*
函数功能：输出线性表
函数参数：结构体指针
返回值 ： void
*/
void Display(struct List *h)
{
struct List *p = h;
int counter = 1;
printf("Position: Data /n");
while (p != NULL)
{
printf(" %d " ,counter);
printf(": %d/n", p->data );
counter++;
p = p->next;
}
}
/*
函数功能：删除某个结点
函数参数：结构体指针，要删除节点数据int
返回值 ： 结构体指针
*/
struct List *Delete(struct List *h , int xdata)
{
struct List *temp = h;
struct List *flag = h;
if ( h == NULL)
{
printf("no link !");
return (h);
}
while (temp->data != xdata && temp->next !=NULL)
{
flag = temp;
temp = temp->next;
}
if (xdata == temp->data) //检查是到了末尾还是已经找到相应节点
{
if (temp == h) //首节点的情况
{
h = temp->next;
}
else
{
flag->next=temp->next;
}
free (temp);
}
else
printf("NO NODE!/n");
return h;
}
/*
函数功能：返回某节点的地址
函数参数：结构体指针，要查找节点数据int
返回值 ： 结构体指针
*/
struct List *Search(struct List *h , int xdata)
{
struct List *temp = h;
if ( h == NULL)
{
printf("no link !");
return (h);
}
while (temp->data != xdata && temp->next !=NULL)
{
temp = temp->next;
}
if (xdata == temp->data) //检查是到了末尾还是已经找到相应节点
return temp;
else
printf("NO Location!/n");
return temp;
}
/*
函数功能：单向链表的逆序
函数参数：结构体指针
返回值 ： 结构体指针
*/
struct List *Revers(struct List *h)
{
struct List *back,*p,*newhead = NULL;
p = h;
while ( p != NULL)
{
back = p->next; //记录当前节点的下一位置，以防链表丢失
p->next = newhead ; //当前节点开始指向前一个节点，此时的newhead初始化一定为NULL
newhead = p ; //newhead指针紧跟着p向后移，一直到最后p指向NULL了，此时newhead为逆序的首结点
p= back; //找到下一个节点
}
return newhead;
}
//感受：从网上看了一个，分明是弄错指针p后移时，没有记录下一节点的位置，造成链表的断开
//他的做法是 back = p;
// p->next = newhead ;
// newhead = p ;
// p= back->next; 这样的话表面上是back记录了下一个节点，实际上他指向的P的next已经被修改为NULL，使得最后一行语句无效
struct List *Delete_all(struct List *h)
{
struct List *temp = NULL;
while (h!= NULL)
{
temp = h;
h=temp->next;
free(temp);
}
return h;
}