C语言—双链表操作
双链表操作
/*双链表的操作:查询、删除、显示、插入。
*双向链表克服单向链表向前查找结点需要执行时间O(n)的缺点
*2008.1.17
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10
typedef struct node *ptNode;
struct node
{
char name[20];
ptNode lLink,rLink;
};/*双链表的结构定义*/
/*双链表的创建*/
ptNode Creat(int n)
{
ptNode head,ptr,newnode;
int i;
if((head=(ptNode)malloc(sizeof(node))) == NULL)
{
printf("cannot find space!\n");
exit(0);
}
head->name[0] = '\0';//头结点初始化
head->lLink = NULL;
head->rLink = NULL;
ptr = head;
for(i=0; i<n; i++)
{
if((newnode=(ptNode) malloc(sizeof(node))) == NULL)
{
printf("cannot find space!\n");
exit(0);
}
ptr->rLink = newnode;//连接新结点
printf("Please input the %d man's name: ",i+1);
scanf("%s",newnode->name);
newnode->lLink = ptr;//定义newnode的连接关系
newnode->rLink = NULL;
ptr = newnode;
}//end for
head->lLink = newnode;
ptr->rLink = head;
return(head);
}
/*查找名字的位置*/
ptNode Search(ptNode head,char *pEle)
{
ptNode ptr;
char *pTemp;
ptr = head->rLink;
while(ptr != head)//以是否回到头结点为结束条件
{
pTemp = ptr->name;//pTemp暂存结点的名字地址
if(strcmp(pTemp,pEle) == 0)
{
return(ptr);
}
else
{
ptr = ptr->rLink;//指向下一结点
}
}
printf("cannot find data!\n");
return NULL;
}
//在选定名字前插入
void Insert(ptNode head,char *prior,char *insertEle)
{
ptNode ptr,newnode;
if((ptr=Search(head,prior)) ==NULL)
{
printf("Can't find the data to insert!\n");
exit(0);
}
if((newnode=(ptNode)malloc(sizeof(node))) == NULL)
{
printf("Can't arrange memory space!\n");
exit(0);
}
strcpy(newnode->name,insertEle);//给新结点加载值
newnode->lLink = ptr->lLink;//前指针指向前结点,先处理以新结点为中心前后关系
newnode->rLink = ptr;//新结点后指针指向定位结点
(ptr->lLink)->rLink = newnode;//前结点的由指针指向新结点
ptr->lLink = newnode;
}
/*打印输出*/
void Print(ptNode head)
{
ptNode ptr;
ptr = head->rLink;
printf("\nNow the double list is:\n");
while(ptr != head)
{
printf("%s ",ptr->name);
ptr = ptr->rLink;
}
printf("\n");
}
/*删除*/
void Delete(ptNode ptr)
{
(ptr->rLink)->lLink = ptr->lLink;//(ptr->rLink)->lLink下一结点的左指针被赋前指针
(ptr->lLink)->rLink = ptr->rLink;
free (ptr);
}
/*主函数*/
void main(void)
{
int number;
char studName[20];
char insertName[20];
ptNode head,searchpoint;
number = N;
puts("Please input the size of the list:");
scanf("%d",&number);
head = Creat(number);
Print(head);
printf("\nPlease input the name which you want to find:\n");
scanf("%s",studName);
searchpoint = Search(head,studName);
printf("the name you want to find is:%s\n",searchpoint->name);
Delete(searchpoint);
Print(head);
printf("Before which element do you want to insert:\n");
scanf("%s",studName);
printf("Enter the student name you want to insert:\n");
scanf("%s",insertName);
Insert(head,studName,insertName);
Print(head);
puts("\n");
}