/*
* File: list.c
* Date: 2010-12-15
* Author: qiang
* Function: 单链表的初始化，建立，插入，查找，删除
*/
#include <stdio.h>
#include <stdlib.h>
//定义数据类型
typedef int ElemType;
//定义节点类型
typedef struct Node //结构体名
{
ElemType data; //单链表数据域
struct Node *next; //单链表指针域
}Node,*LinkedList; //结构体变量名
//单链表初始化
LinkedList LinkedListInit()
{
Node *L;
L=(Node*)malloc(sizeof(Node)); //申请节点空间
if(L==NULL)
printf("申请内存空间失败");
L->next=NULL; //初始化长度为0
return L;
}
//单链表建立-头插法
LinkedList LinkedListCreatH()
{
Node* L;
L=(Node*)malloc(sizeof(Node));
if(L==NULL)
printf("申请内存空间失败");
L->next=NULL; //L为尾节点
ElemType x;
while(scanf("%d",&x)!=EOF) //Windows中，CTRL+Z触发EOF；Linux中CTRL+D触发EOF
{
Node* p; //创建当前节点
p=(Node*)malloc(sizeof(Node));
p->data=x;
p->next=L->next;
L->next=p; //L节点前移，实现头插法
}
return L;
}
//单链表建立-尾插法
LinkedList LinkedListCreatT()
{
Node* L;
L=(Node*)malloc(sizeof(Node));
L->next=NULL; //初始化一个空链表
Node* r; //定义一个节点，始终指向尾节点
r=L; //起初r指向L
ElemType x;
while(scanf("%d",&x)!=EOF)
{
Node* p;
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p; //将结点插入到表头L-->|1|-->|2|-->NULL
r=p;
}
r->next=NULL; //r始终为尾节点
return L;
}
//单链表插入：在第i个位置(i>=1)后插入元素x
LinkedList LinkedListInsert(Node* L,int i,ElemType x)
{
//首先找出i的前驱节点
Node* pre=L;
int tmp;
for(tmp=0;tmp<i;tmp++)
pre=pre->next;
//在前驱节点之后插入元素x
Node* p;
p=(Node*)malloc(sizeof(Node));
p->next=pre->next;
p->data=x;
pre->next=p;
return L;
}
//单链表删除：删除第i个元素（i>=0）
LinkedList LinkedListDel(Node* L,int i)
{
//找到第i个元素的前驱节点
int tmp;
Node* pre;
pre=L;
for(tmp=0;tmp<i-1;tmp++)
pre=pre->next;
//将前驱节点直接连接下一节点
Node* q; //缓存删除的节点
q=pre->next;
pre->next=q->next;
return L;
}
//测试主函数
int main()
{
LinkedList list,start;
/*
printf("清输入单链表的数据： \n");
list=LinkedListCreatH();
for(start=list->next;start!=NULL;start=start->next)
printf("list data:%d \n",start->data);
*/
printf("清输入单链表的数据： \n");
list=LinkedListCreatT();
for(start=list->next;start!=NULL;start=start->next)
printf("list data:%d \n",start->data);
int i,x;
printf("请输入插入的位置i=：\n");
scanf("%d",&i);
printf("请输入插入的数据x=: \n");
scanf("%d",&x);
LinkedListInsert(list,i,x);
printf("插入后的链表数据如下：\n");
for(start=list->next;start!=NULL;start=start->next)
printf("list data:%d \n",start->data);
int j;
printf("请输入要删除的位置i=:");
scanf("%d \n",&j);
LinkedListDel(list,j);
printf("删除后的链表数据如下：\n");
for(start=list->next;start!=NULL;start=start->next)
printf("list data: %d \n",start->data);
return 0;
}
|
