程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C實現通用數據結構--單鏈表，通用數據結構--單鏈

C實現通用數據結構--單鏈表，通用數據結構--單鏈

編輯：C++入門知識

C實現通用數據結構--單鏈表，通用數據結構--單鏈

單鏈表概述

單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。

從概念上講，可以把鏈表想象成一系列連續的元素，然而，由於這些元素是動態分配的（C語言中使用malloc），切記這些元素通常實際上都是分散在內存空間的

本文地址：http://www.cnblogs.com/archimedes/p/c-datastruct-linklist.html，轉載請注明源地址。

單鏈表的接口定義：

1、list_init

void list_init(List *list, void (*destroy)(void *data));

返回值 void

描述初始化由參數list指定的鏈表，該函數必須在鏈表做其他操作之前調用，當調用list_destroy時，destroy參數提供了一種釋放動態分配數據的方法。如果鏈表采用malloc動態分配的數據，destroy應該設置為free來釋放這些數據

復雜度 O(1)

2、list_destroy

void list_destroy(List *list);

返回值 void

描述銷毀由參數list指定的鏈表，調用該函數以後任何函數都不能再執行，除非重新執行list_init函數。list_destroy將list中的所有元素都移除，每移除一個元素都會調用此函數

復雜度 O(n) n為鏈表元素的個數

3、list_ins_next

int list_ins_next(List *list, ListElmt *element, const void *data);

返回值如果插入元素成功返回0，否則返回-1

描述在指定的list的element元素後面插入一個元素，如果element為NULL，則在鏈表的頭部插入新的元素，該元素包含一個指向data的指針

復雜度 O(1)

4、list_rem_next

int list_rem_next(List *list, ListElmt *element, void **data);

返回值如果移除元素成功返回0，否則返回-1

描述移除在指定的list的element後面的那個元素，如果element為NULL，則移除鏈表的頭元素，調用返回後，data指向已經移除元素的數據

復雜度 O(1)

5、list_size

int list_size(const List *list);

返回值如果list中元素的個數

描述這是一個宏，用來計算指定list中元素的個數

復雜度 O(1)

6、list_head

ListElmt *list_head(const List *list);

返回值指向鏈表頭元素的指針

描述這是一個宏，返回由參數list指定的鏈表頭元素的指針

復雜度 O(1)

7、list_tail

ListElmt *list_tail(const List *list) ((list)->tail);

返回值指向鏈表尾元素的指針

描述這是一個宏，返回由參數list指定的鏈表尾元素的指針

復雜度 O(1)

8、list_is_head

int list_is_head(const ListElmt *element);

返回值如果element元素是鏈表頭元素返回1，否則返回-1

描述這是一個宏，用來判斷element元素是否是list的頭元素

復雜度 O(1)

9、list_is_tail

int list_is_tail(const ListElmt *element);

返回值如果element元素是鏈表尾元素返回1，否則返回-1

描述這是一個宏，用來判斷element元素是否是list的尾元素

復雜度 O(1)

10、list_data

void *list_data(const ListElmt *element);

返回值結點中保存的數據

描述這是一個宏，返回由element元素中保存的數據

復雜度 O(1)

11、list_next

ListElmt *list_next(const ListElmt *element) ;

返回值返回element所指定結點的下一個結點

描述這是一個宏，返回鏈表中element所指定結點的下一個結點

復雜度 O(1)

單鏈表的實現和分析

抽象數據類型的頭文件（list.h）：

#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
//為單鏈表的結點定義一個結構體.   
typedef struct ListElmt_ {
    void               *data;   //數據域
    struct ListElmt_   *next;    //指針域

} ListElmt;

//為單鏈表定義一個結構體.               
typedef struct List_ {
    int                size;     //容量
    int                (*match)(const void *key1, const void *key2);    //匹配函數
    void               (*destroy)(void *data);    //撤銷操作
    ListElmt           *head;   //頭指針  
    ListElmt           *tail;   //尾指針

} List;

//公共接口
void list_init(List *list, void (*destroy)(void *data));

void list_destroy(List *list);

int list_ins_next(List *list, ListElmt *element, const void *data);

int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)

#define list_head(list) ((list)->head)

#define list_tail(list) ((list)->tail)

#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define list_data(element) ((element)->data)

#define list_next(element) ((element)->next)

#endif

初始化單鏈表：

void list_init(List *list, void (*destroy)(void *data)) {  //初始化list                              
    list->size = 0;
    list->destroy = destroy;   //設置為定義的析構函數
    list->head = NULL;
    list->tail = NULL;
    return;
}

回收單鏈表：

void list_destroy(List *list) {
//移除每一個元素   
    while (list_size(list) > 0) {
           if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {  //不斷地移除鏈表的頭結點
                  list->destroy(data);  //調用一個用戶定義的函數來釋放動態分配的數據. 
           }
    }
    //現在沒有操作了,釋放結構體作為預防措施
    memset(list, 0, sizeof(List));
    return;
}

插入新節點作為指定結點的直接後繼結點:

int list_ins_next(List *list, ListElmt *element, const void *data) {
    ListElmt *new_element;     //為結點動態分配存儲空間
    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)  //假如分配失敗
          return -1;
    // 將元素插入鏈表  
    new_element->data = (void *)data;
    if (element == NULL) {
        //插入到鏈表的頭部
        if (list_size(list) == 0)
            list->tail = new_element;
        new_element->next = list->head;
        list->head = new_element;
    } else {
        //插入到除了鏈表頭部以外指定的其他地方
        if (element->next == NULL)
            list->tail = new_element;
        new_element->next = element->next;
        element->next = new_element;
    }
    list->size++; //表長增加
    return 0;
}

刪除指定結點的直接後繼結點:

int list_rem_next(List *list, ListElmt *element, void **data) {
    ListElmt *old_element;
    //不允許從一個空的list中移除元素. 
    if (list_size(list) == 0)
        return -1;
    // 從list中移除元素.
    if (element == NULL) {
        // 移除表頭的結點. 
           *data = list->head->data;
        old_element = list->head;
        list->head = list->head->next;
        if (list_size(list) == 1)   //如果list只有一個元素，則直接刪除尾結點
            list->tail = NULL;
    } else {
        // 移除非頭結點. 
        if (element->next == NULL)
            return -1;
        *data = element->next->data;
        old_element = element->next;
        element->next = element->next->next;
        if (element->next == NULL)  //移除指定結點後，後繼為NULL，則用尾結點指向
            list->tail = element;
    }
    //釋放分配的抽象數據類型.  
    free(old_element);
    //調整list的長度.           *
    list->size--;
    return 0;
}

注意：list_size、list_head、list_tail、list_is_head、list_is_tail、list_data、list_next 這些宏實現了鏈表中的一些簡單操作，它們提供了快速訪問和檢測結構體成員的能力。這些操作的時間復雜度都是O(1)

完整的測試代碼如下：

// Completed on 2014.10.22 21:00
// Language: C99
//
// 版權所有（C）codingwu   (mail: oskernel@126.com) 
// 博客地址：http://www.cnblogs.com/archimedes/
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

static void print_list(const List *list) {
    ListElmt *element;
    int *data, i;
    fprintf(stdout, "List size is %d\n", list_size(list));
    i = 0;
    element = list_head(list);
    while (1) {
        data = list_data(element);
        fprintf(stdout, "list[%03d]=%03d\n", i, *data);
        i++;
        if (list_is_tail(element))
            break;
        else
            element = list_next(element);
    }
    return;
}

int main(int argc, char **argv) {

    List list;
    ListElmt *element;
    int *data, i;

    //初始化list
    list_init(&list, free);
    element = list_head(&list);
    for (i = 10; i > 0; i--) {
        if ((data = (int *)malloc(sizeof(int))) == NULL)
            return 1;
        *data = i;
        if (list_ins_next(&list, NULL, data) != 0)  //逐個插入元素
            return 1;

    }
    print_list(&list);    //打印初始list
    element = list_head(&list);  //指向頭結點
    for (i = 0; i < 7; i++)
        element = list_next(element);

    data = list_data(element);
    fprintf(stdout, "Removing an element after the one containing %03d\n", *data);

    if (list_rem_next(&list, element, (void **)&data) != 0)  //刪除指定結點
        return 1;
    print_list(&list);
    fprintf(stdout, "Inserting 011 at the tail of the list\n");
    *data = 11;
    if (list_ins_next(&list, list_tail(&list), data) != 0)   //插入指定結點
        return 1;
    print_list(&list);
    fprintf(stdout, "Removing an element after the first element\n");

    element = list_head(&list);
    if (list_rem_next(&list, element, (void **)&data) != 0)
       return 1;

    print_list(&list);

    fprintf(stdout, "Inserting 012 at the head of the list\n");

    *data = 12;
    if (list_ins_next(&list, NULL, data) != 0)
        return 1;

    print_list(&list);

    fprintf(stdout, "Iterating and removing the fourth element\n");

    element = list_head(&list);
    element = list_next(element);
    element = list_next(element);

    if (list_rem_next(&list, element, (void **)&data) != 0)
        return 1;

    print_list(&list);

    fprintf(stdout, "Inserting 013 after the first element\n");

    *data = 13;
    if (list_ins_next(&list, list_head(&list), data) != 0)
        return 1;

    print_list(&list);

    i = list_is_head(&list, list_head(&list));
    fprintf(stdout, "Testing list_is_head...Value=%d (1=OK)\n", i);
    i = list_is_head(&list, list_tail(&list));
    fprintf(stdout, "Testing list_is_head...Value=%d (0=OK)\n", i);
    i = list_is_tail(list_tail(&list));
    fprintf(stdout, "Testing list_is_tail...Value=%d (1=OK)\n", i);
    i = list_is_tail(list_head(&list));
    fprintf(stdout, "Testing list_is_tail...Value=%d (0=OK)\n", i);

    fprintf(stdout, "Destroying the list\n");
    list_destroy(&list);
    return 0;

}

數據結構單鏈表用c語言怎實現

# include<stdio.h>
# include<stdlib.h>
typedef int datatype;
typedef struct node{
datatype data;
struct node *next;
}LinkList;
LinkList *head,*p,*s;
int i,j,x,count,length,choices;
LinkList (*CreatList)()//創建單鏈表
{
int t;
LinkList *r;
head=(LinkList*)malloc(sizeof(LinkList));
r=head;
scanf("%d",&t);
while(t!=-1){
s=(LinkList*)malloc(sizeof(LinkList));
s->data=t;
r->next=s;
r=s;
scanf("%d",&t);
}
r->next=NULL;
return head;
}
LinkList DispList(LinkList *head)//輸出單鏈表
{
for(p=head->next;p;p=p->next)
printf("%5d",p->data);
printf("\n");
}
int ListLength(LinkList *head)//計算單鏈表長度並輸出
{
length=0;
p=head->next;
while(p!=NULL){
p=p->next;
length++;
}
printf("%5d\n",length);
}
LinkList GetElem(LinkList *head,int i)//查找某一元素並輸出
{
j=0;
LinkList *p;
p=head;
scanf("%d",&i);
while((p->next!=NULL)&&(j<i)){
p=p->next;
j++;
}
if(i==j) printf("%5d\n",p->data);
else printf("NULL\n");
}
LinkList LocateElem(LinkList *head,int x)//查找某一元素的位置並輸出
{
p=head->next;
count=1;
scanf("%d",&x);
while(p!=NULL){
if(p->data!=x){p=p->next; count++;}
else break;
}
if(count<=length) printf("%5d\n",count);
else printf("error\n");
}
LinkList ListInsert(LinkList *head,int i,datatype x)//在某一位置插入某一元素
{
j=1;
p=head->......余下全文>>

c數據結構實現單鏈表的創建、插入、刪除、打印與查詢

#include <iostream>
using namespace std;

typedef struct node
{
char data;
struct node *next;
}link;

link * get(link *l, int i)
{
link *p;int j=0;
p=l;
while((j<i) && (p->next!=NULL))
{p=p->next;j++;}
if(j==i)
return p;
else
return NULL;
}

link * ins (link *l, char ch,int i)
{ link *p,*s;
p=get(l,i-1);
if(p==NULL)
cout<<"輸入有誤"<<endl;
else
{
s=(link *)malloc(sizeof(link));
s->data=ch;
s->next=p->next;
p->next=s;
}
return l;
}

link * find(link *l, char ch)
{
link *p; int i=0; int j=0;
p=l;

while(p!=NULL)
{ i++;
if(p->data!=ch)
p=p->next;
else {cout<<"您查找的數據在第"<<i-1<<"個位置."<<endl;
j=1;p=p->next;
}

}
if(j!=1)
cout<<"您查找的數據不在線性表中."<<endl;
return l;
}

link * del(link *l, int i)
{
link *p,*s;
p=get(l,i-1);
if(p==NULL)
cout<<"輸入有誤"<<endl;
else
{
s=p->next;
p->next=s->next;
free(s);
}
return l;
}

link * add(link *l )
{
link *p,*s;
cout<<"請輸入一串單字符數據，以*結束！"<<endl;
char ch;
link *HEAD;
link *R,*P,*L;
HEAD=(link *)malloc(sizeof(link));
HEAD->next=NULL;
R=HEAD;
getchar();
ch=getchar();
while(ch!='*')
{
P=(link *)malloc(sizeof(link));
P->data=ch;P->next=NULL;
R->next=P;R=R->next;
getchar();
ch=getchar();

}

L=HEAD;
cout<<"當前輸入的線性表為："<<endl;
P=L;P=P->next;
if(L!=NULL)......余下全文>>