创建单线性链表的不同表示方法和操作，创建线性表示
创建单线性链表，常见的有头插法、尾插法创建线性链表，常见的操作有：创建链表、查找、删除、增加元素、求逆链等操作。
这里首先用头插法创建链表：
//头指针唯一确定一个单链表
#define MaxSize 15
typedef int elem_type ;
typedef struct linklist
{
elem_type data;
struct linklist *next;
} Linklist;
//头插入法建立链表：每次将头结点的指针赋值给新结点，然后将新节点赋值给头结点指针
Linklist *CreateList ()
{
Linklist *head,*p;
head =(Linklist *)malloc(sizeof(Linklist));
head->next=NULL;
// p =(Linklist *)malloc(sizeof(Linklist));
int i;
cout<<"随机产生一个数字："<<endl;
for(i=0;i<MaxSize;i++)
{
int data;
data =rand()%100;
p =(Linklist *)malloc(sizeof(Linklist));
cout<<"第"<<i<<"个数是"<<data<<endl;
p->data =data;
p->next=head->next;
head->next=p;
}
return head;
} //利用头插法创建的链表有什么特点呢？
这里可以写个查找函数来说明：
定义一个查找函数：
//查找(取出第i个数的值)
elem_type Get_Elem(Linklist *L, int i)
{
int j;
Linklist *p;
p=L->next;
if((i>MaxSize) && (i< 0))
cout<<"输入有效的i值";
for(j=0;j<i-1;j++)
{
p=p->next;
//flag->next++; //链表不是矩阵，指针自加1不是指向下一个结点，那是矩阵里可以这样。
}
return p->data;
} 编译一下：结果如下
//主函数如下：
int main()
{
Linklist *Q;
Q=CreateList();
int i;
cout<<"输入想要查找的元素号i=";
cin>>i;
int getNum = Get_Elem( Q , i);
cout<<"第"<<i<<"个元素是"<<getNum<<endl;
//Insert_Elem(Q, 3,5);
while(1);
return 0;
} 
根据运行结果可知道：对于头插法，输入的结点次序和生成的链表次序相反。
还有可以有：删除元素和增添元素的函数体：
//删除链表中的某个结点
void Delete_Linklist(Linklist *L,elem_type i)
{
Linklist *p,*q;
p=L->next;
int j=0;
if(i<0 && i>MaxSize )
cout<<"j输入有效的i值";
else
{
while((p->next != NULL)&&(j<i-1))
{
p=p->next; //寻找第i个结点
++j;
}
q=p->next;
p->next=q->next;
free(q);
}
}
//添加结点（在第i个节点处添加一个值）
void Insert_Elem(Linklist *L, int i, elem_type Number)
{
int j;
Linklist *p,*q;
p=L->next;
if((i>MaxSize) && (i< 0))
cout<<"输入有效的i值";
for(j=0;j<i-1;j++)
{
p=p->next;
//flag->next++; //链表不是矩阵，指针自加1不是指向下一个结点，那是矩阵里可以这样。
}
if(i==j+1)
{
q=(Linklist *)malloc(sizeof(Linklist));
q->data=Number;
q->next=p->next;
p->next=q;
}
// return p;
}
问题分析：为什么头插法的数据元素顺序和链表中结点顺序相反？
循环第一次时：
p->data =data; //数据元素第一次赋值
p->next=head->next; //循环赋值，第一次将NULL赋给p->next,
head->next=p; //第一次赋值后的p赋给head->next;
循环第二次时：
p->data =data; //数据元素第二次赋值
p->next=head->next; //循环赋值，第二次将 （第一次赋值后的<span style="font-family: Arial, Helvetica, sans-serif;">head->next</span><span style="font-family: Arial, Helvetica, sans-serif;">）赋给p->next,</span>
head->next=p; //第二次赋值后的p赋给head->next;
所以新赋值进来的结点更靠近head->next.
#include<stdio.h>
#define LEN sizeof(struct number)
struct number /*定义编号和数字*/
int name;
int num;
struct number * next;
};
struct number * create() /*建立链表函数*/
{
struct number * head,* new,* tail,* p;
int count=0;
while(1)
{
new=(struct number *)malloc(LEN);
printf("input Name and Number\n");
scanf("%d %d",&new->name,new->num); /*用户输入编号和数字*/
if(new->name==0)
{
free(new);
break;
}
else if(count==0)
{
head=new;
tail=new;
}
else
{
tail->next=new;
tail=new;
}
count++;
}
tail->next=NULL;
return(head);
}
struct number * delist(struct number *head,int name) /*删除数字的函数*/
{
struct number * p0,* p1;
p1=head;
if(head==NULL)
{
printf("\nempty list!\n");
}
else
if(p1->name==name) /*找到相同编号*/
head=p1->next;
else
{
while(p1->name!=name&&p1->next!=NULL) /*逐一排查*/
{
p0=p1;
p1=p1->next;
}
if(p1->name==name)
{
p0->next=p1->next;
printf("The node is deleted\n");
}
else
printf("The node can not been foud!\n");
}
return head;
}
struct number * insert(struct number * head,struct number * new)
{ ......余下全文>>
1.单链表的类型定义
typedef struct Node *PNode; /* 结点指针类型 */
struct Node /* 单链表结点结构 */
{
DataType data; /* 值域 */
struct Node *next; /* 指针域 */
};
为提高可读性,可定义单链表类型如下:
typedef struct Node *LinkList;
LinkList list; /* 定义一单链表list */
PNode p; /* 定义一单链表结点指针
则指针p所指结点的两个域表示为：
值 域： p->data
指针域： p->next
注：设置表头结点的目的是统一空链表与非空链表的操作，简化链表操作的实现。带头结点的空链表表示为：list->next==NULL;而不带头结点的空链表只能表示为list==NULL;
单链表的常用算法(带头结点)
算法 1 创建空单链表LinkList createNullist_link( void )
分析：申请一表头结点的存储空间，并将该结点指针域置空
LinkList CreateNullist_link(void)
{
LinkList list=(LinkList)malloc(sizeof(struct Node));
//申请表头结点存储空间
if( list != NULL) list->next=NULL;
else printf(“Out of space!\n”); //创建失败
return(list);
}
注：算法中malloc为内存申请函数，需头文件stdlib.h支持。
算法 2 单链表的插入 int insert_link( LinkList list, PNode p, DataType x )
插入结点算法：
首先生成待插入结点q,将其值域置为x，然后通过修正指针将结点q插入到结点p之后。
插入实现：
q->data=x; //生成待插入结点
q->next=p->next;
p->next=q;
算法 3 单链表结点的删除 int delete_link(LinkList list, DataType x )
删除结点算法： 首先在list 带有头结点的单链表中找到第一个值为x的结点q，并记录其前驱结点的位置p,然后通过指针修正删除结点q。
删除实现：
q=p->next;
p->next=q->next;
free(q);
...余下全文>>
