线性表链式存储-使用c语言实现

单链表使用c语言实现

//单链表存储结构 
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct Node{
    ElemType data;

struct Node *next; 
} Node;
typedef struct Node *LinkList;

//获取链表的长度 
Status getListLength(LinkList L){
int i = 0; //计数器
while(L->next){
        L = L->next;
        i++;
    } 
return i;
}

//单链表的读取,用e返回L中的第i个元素的值 , 0 < i < L.length
Status getElem(LinkList L, int i, ElemType *e){ 
int j = 1;
    LinkList p; 
    p = L->next;    //p为第一个节点
while(p && j < i){ //p不为null 
        p = p->next;
        j++; 
    }
if(!p || i > j){
return ERROR;   //查找的元素不存在 
    }
    *e = p->data;   //去第i个元素的数据
return OK; 
} 

//单链表的创建,随机产生n个随机数,建立带头结点的单链表(头插法) 
Status createListHead(LinkList *L, int n){
    LinkList p;
int i;
    srand(time(0)); //初始化随机种子
    *L = (LinkList)malloc(sizeof(Node)); //建立链表 
    (*L)->next = NULL;  //定义一个头结点 
for(i = 0; i < n; i++){     //生成结点 
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand() % 100 + 1; //产生100以内的数字 
        p->next = (*L)->next;   
        (*L)->next = p; //插入到表头 
    }   
return OK;  
}

//单链表的创建,随机产生n个随机数,建立带头结点的单链表(未插法) 
Status cretateListTail(LinkList *L, int n){
    LinkList p, q;
int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));    //建立一个新的链表 
    q = *L;
for(i = 0; i < n; i++){
        p = (LinkList)malloc(sizeof(Node));//产生一个新的节点
        p->data = rand() % 100 + 1; //产生一个100以内的数字 
        q->next = p;    //新节点添加到链表的末尾 
        q = p;      //新节点定义为未节点 
    }
    q->next = NULL; //链表的最后一个元素指向null
return OK; 
} 

//遍历单链表,输出值
void listTraverse(LinkList L){
if(L->next == NULL){
printf("链表为空");
    }else{
        LinkList p;
        p = L->next;
while(p != NULL){
printf("%d ",p->data);
            p = p->next;
        }
printf("\n");   
    }
}

//链表的插入 将e插入到第i个位置之前 0 < i < listLenght + 1 
//定位到第i个节点,生成一个新的节点,数据e保存在新的节点中,最后插入到链表中 
Status listInsert(LinkList *L, int i, ElemType e) {
int j = 1;
    LinkList p, s;
    p = *L; 
while(p && j < i){ //p不为null 
        p = p->next;
        j++;
    }
if(!p || i < j){    //查找失败
return ERROR;
    }
    s = (LinkList)malloc(sizeof(Node)); //生成一个新的节点
    s->data = e;
    s->next = p->next;  //插入新节点 
    p->next = s; 
return OK;
}

//链表删除 从链表中删除第i个元素,将删除的元素保存到e中 
Status ListDelete(LinkList *L, int i, ElemType *e){
int j = 1;
    LinkList p, q; 
    p = *L;
while(p && i > j){
        p = p->next;
        j++;
    }
if(!p || j > i){
return ERROR;   //查找失败 
    }
    q = p->next;
    *e = q->data;   //保存要删除的数据
    p->next = q->next;  //将q的后继赋值给p的后继
free(q);    //释放空间 
return OK; 
} 

//删除所有的节点
Status clearList(LinkList *L) {
    LinkList p, q;
    p = (*L)->next;
while(p){       //循环删除每一个节点 
        q = p->next;
free(p);
        p = q;
    }
    (*L)->next = NULL;  //头结点 
return OK;
}

int main(void){
    LinkList L;
    cretateListTail(&L, 10);
printf("初始化10个元素,分别是: \n"); 
    listTraverse(L);
    ElemType e; 
    getElem(L, 4, &e);
printf("链表中第4个元素是: %d \n",e); 
printf("链表的长度是: %d \n",getListLength(L));
    listInsert(&L, 4, 12);
printf("在链表第4个元素之前插入12 \n"); 
    listTraverse(L);
    ListDelete(&L, 5, &e);
printf("在链表中删除第5个元素 \n"); 
    listTraverse(L);
    clearList(&L);
printf("清除链表之后的元素: \n"); 
    listTraverse(L);
return OK;
}

• 头指针与头结点的异同

  • 头指针
    
    1. 头指针是指链表指向第一个结点的指针,若链表有头结点,则指向头结点的指针.
    2. 头指针具有标识作用,所以常用头指针冠以链表的名称.
    3. 无论链表是否为空,头指针均不为空.头指针是链表的必要元素.
  • 头结点
    
    1. 头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意义(可以存放链表的长度)
    2. 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作统一了.
    3. 头结点不一定是链表必要素.

• 单链表结构和顺序存储结构的对比:

  • 存储分配方式
    
    1. 顺序存储结构用一段连续的存储单元一次存储线性表的数据元素.
    2. 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素.
  • 时间性能
    
    1. 查找
       
       • 顺序存储结构o(1)
       • 单链表o(n)
    2. 插入和删除
       
       • 顺序存储结构需要平均移动表长一半的元素,时间为o(n).
       • 单链表在找出某位置的指针后,插入和删除时间仅为o(1).
  • 空间性能
    
    1. 顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢.
    2. 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制.

1.如果线性表需要频繁的查找,很少进行插入操作,宜采用顺序存储结构.如果需要频繁插入和删除是,宜采用单链表结构.
2. 当线性表中的元素个数变化较大或者根本就不知道有多大时,最好用单链表结构,这样可以不需要考虑存储空间的大小问题.而如果知道了线性表的大致长度,比如一年12个月,这种用顺序存储结构效率会比较高.

个人之前写了关于 “线性表顺序存储结构-使用c语言实现”的博客,可以进行对比学习 地址: http://blog.csdn.net/u010187139/article/details/46659943