Chinaunix
标题:
单链表
[打印本页]
作者:
craneee
时间:
2007-04-15 20:16
标题:
单链表
//链式存储结构 -- 单链表
#include stdio.h>
#include stdlib.h>
#include string.h>
typedef struct node{ //结点类型定义
int data; //结点的数据域
struct node *next; //结点的指针域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
ListNode *pHead = NULL;
//改进:使用与线分配好的静态数组避免malloc失败
//use static buffer
//int a[100] = {0};
//用尾插法建立带头结点的单链表 O(n)
LinkList CreatListR1(void)
{
char ch;
LinkList head=(ListNode *)malloc(sizeof(ListNode));//生成头结点
ListNode *s,*r; //工作指针
r=head; // 尾指针初值也指向头结点
while((ch=getchar())!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
s->data=ch; //将读入的数据放入新结点的数据域中
r->next=s;
r=s;
}
r->next=NULL;//终端结点的指针域置空,或空表的头结点指针域置空
return head;
}
//尾插法建循环单链表 返回单链表的头指针 O(n)
LinkList CreatListB(int len)
{
LinkList head = NULL; //头指针
ListNode *s = NULL; //工作指针
ListNode *r = NULL; //工作指针(尾)
for(int i=1; i=len; ++i){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
s->data = i;
if (head==NULL)
head=s;//新结点插入空表
else
r->next=s;//将新结点插到*r之后
r=s;//尾指针指向新表尾
}
r->next = head;//头尾相连
return head;
}
//头插法建循环单链表 返回单链表的头指针 O(n)
LinkList CreatListF(int len)
{
LinkList head = NULL; //头指针
ListNode *s = NULL; //工作指针
ListNode *r = NULL; //工作指针(尾)
for(int i=1; i=len; ++i){
s = (ListNode *)malloc(sizeof(ListNode));
s->data = i;
s->next = head;
if(head!=NULL)
head = s;
else
r = head = s;
}
r->next = head;//头尾相连
return head;
}
//打印循环链表
void printList(LinkList p)
{
ListNode *head = p;
ListNode *tmp = p;
if(p->next == p){
printf("%d\n", tmp->data);
return;
}
do{
printf("%d ", tmp->data);
tmp = tmp->next;
}while(head != tmp);
putchar('\n');
}
int main(void)
{
int len;
printf("input len: ");
scanf(" %d", &len);
LinkList p1 = CreatListF(len);
printList(p1);
LinkList p2 = CreatListB(len);
printList(p2);
return 0;
}
本文来自ChinaUnix博客,如果查看原文请点:
http://blog.chinaunix.net/u/5933/showart_278538.html
欢迎光临 Chinaunix (http://bbs.chinaunix.net/)
Powered by Discuz! X3.2