单链表
#include
typedef int elemtype;
typedef struct node //线性表的单链式存储结构 {
elemtype data;
struct node *next;
} LNode, *LinkList; /*结点类型名*/
//上面定义了LNode 是节点的类型，LinkList是指向LNode节点类型的指针类型。
//可定义一个LinkList类型的变量L，如LinkList L，作为单链表的头指针，来表示一个单链表。若L为“空”（L=NULL），则所表示的线性表为“空”表，其长度ｎ为０。 若定义了如下指针
LNode *p;或LinkList p;
则语句P=(LNode*)malloc(sizeof(LNode))表示分配一个LNode型的结点的存储空间，并将其地址赋值给变量p，p所指结点为*p，*p的类型为LNode型，所以该结点的数据域为(*p).data或p->data，指针域为(*p).next或p->next，而语句free(p)则表示释放该结点所占用的存储空间。
//typedef LNode* LinkList;/*链表的类型*/ //LinkList 等价于 LNode * //LinkList H=NULL;
LinkList InitList() {
LinkList H;
H=(LinkList)malloc(sizeof(LNode)); H->data=9999; H->next=NULL; return H; }
//初始化带头结点链表 //初始化不带头结点的链表 LinkList InitLinkList() LinkList InitLinkList() { { LinkList H; LinkList H; H= (LinkList)malloc(sizeof(LNode)); H=NULL; H->next=NULL; return H; return H; } }
1
//不带头结点的单链表创建 LinkList CreateNoHeadList() {
LinkList L=NULL; LNode *s,*r=NULL; elemtype x;
scanf(\ while(x!=FLAG) {
s=(LNode *)malloc(sizeof(LNode)); s->data=x;
if(L==NULL) L=s; else r->next=s; r=s;
scanf(\ }
if(r!=NULL) r->next=NULL; return (L); }
//带头结点的头插法
LinkList CreateListFromHead1() {
elemtype x; LNode *s; LinkList H;
H=InitLinkList(); scanf(\ while(x!=FLAG) {
s=(LinkList )malloc(sizeof(LNode)); s->data=x;
s->next=H->next; H->next=s;
scanf(\ }
return H; }
//带头结点的单链表创建 LinkList CreateHeadList() {
LinkList L; LNode *s,*r; elemtype x;
L=(LinkList )malloc(sizeof(LNode)); L->next=NULL; r=L;
scanf(\ while(x!=FLAG) {
s=(LNode *)malloc(sizeof(LNode)); s->data=x;
// if(L==NULL) L=s; // else
r->next=s; r=s;
scanf(\ }
if(r!=NULL)r->next=NULL; return (L); }
//不带头结点的头插法
LinkList CreateListFromHead2() {
elemtype x; LNode *s;
LinkList H=NULL; scanf(\ while(x!=FLAG) {
s=(LinkList )malloc(sizeof(LNode)); s->data=x; s->next=H; H=s;
scanf(\ }
return H; }
2
//带头结点的尾插法
LinkList CreateListFromTail1() {
elemtype x; LNode *s,*r; LinkList H;
H=InitLinkList(); r=H;
scanf(\ while(x!=FLAG) {
s=(LinkList )malloc(sizeof(LNode)); s->data=x;
s->next=NULL; r->next=s; r=s;
scanf(\ }
return H; }
//带头结点的输出
void PrnLinkList(LinkList H) {
LNode *p=H->next;
while(p!=NULL) //while(p) {
printf(\ p=p->next;
}
printf(\}
//不带头结点的尾插法
LinkList CreateListFromTail2() {
elemtype x;
LNode *s,*r=NULL; LinkList H=NULL; scanf(\ while(x!=FLAG) {
s=(LinkList )malloc(sizeof(LNode)); s->data=x;
s->next=NULL; if(H==NULL) H=s; else r->next=s; r=s;
scanf(\ }
return H; }
//不带头结点的输出
void PrnLinkList(LinkList H) {
LinkList p=H; //LinkList p;p=H; while(p!=NULL) //while (p) {
printf(\ p=p->next; }
printf(\}
3
//带头结点的求表长算法 int LenList(LinkList L) {
LNode *p=L->next; int len=0;
while(p!=NULL) {
len++; p=p->next; }
return len; }
//带头结点的链表逆置 void reverse(LinkList H) {
LNode *p,*q; p=H->next;
H->next=NULL; while(p)
{ q=p;p=p->next; q->next=H->next; H->next=q; } }
//不带头结点的逆置
LinkList reverse2(LinkList H) {
LNode *p,*q; p=H;
H=NULL; while(p) {
q=p;p=p->next; q->next=H; H=q; }
return H; }
//不带头结点的求表长算法 int LenList(LinkList L) {
LNode *p=L; int len=0;
while(p!=NULL) {
len++; p=p->next; }
return len; }
//不带头结点的链表逆置 void reverse1(LinkList H) {
LNode *p,*q; p=H;
H=NULL; while(p) {
q=p;p=p->next; q->next=H; H=q; } }
//不带头结点的逆置，二重指针void reverse3(LinkList *H) {
LNode *p,*q; p=(*H);
(*H)=NULL; while(p) {
q=p;p=p->next; q->next=(*H); (*H)=q; } }
4
//查找第i个结点
LNode * GetItem(LinkList L,int i) {
LNode *p=L; int j=0;
while(p->next!=NULL&&j!=i) {
j++;
p=p->next; }
if(j==i) return p; else return NULL; }
//在第i个位置上插入值为x的结点 int InsItem(LinkList L,elemtype item,int i) {
LNode *pre,*s; int k;
//pre=GetItem(L,i-1); pre=L; k=0;
while(pre!=NULL&&k /*在第i个元素之前插入，则先找到第i-1个数据元素的存储位置,使指针Pre指向它*/ { pre=pre->next; k=k+1; } if(k!=i-1) /*即while循环是因为pre=NULL或i<1而跳出的，所以一定是插入位置不合理所致*/ { printf(\插入位置不合理！\\n\ return 0; } else { s=(LNode *)malloc(sizeof(LNode)); s->data=item; s->next=pre->next; pre->next=s; return 1; } } 5 //删除第i个结点 int DelItem(LinkList L,int i) { LNode *pre,*s; int k; /* pre=GetItem(L,i-1); if(pre==NULL) {printf(\第i-1个结点不存在\ if(pre->next==NULL) {printf(\第i个结点不存在\ */ pre=L; k=0; if(i==0) { printf(\删除结点的位置i不合理!\\n\ return -1; } while(pre->next!=NULL && k s=pre->next; pre->next=s->next; free(s); return 1; } int main() { LinkList L; // L=InitLinkList(); printf(\输入数值，以-1结束\\n\ L=CreateListFromTail1(); printf(\创建链表成功\\n\ PrnLinkList(L); return 0; } 6