顺序链表

顺序存储链表结构体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef struct _tag_SeqList /* 头节点,记录表的信息 */
{
    int capacity;   /* 表容量 */
    int length;     /* 表长度 */
    int *node;      /* node[capacity],为指针素组 char **node; */
}TSeqList;

typedef void SeqList;
typedef void SeqListNode;

SeqList *SeqList_Create(int capacity);  /* 创建顺序表 */
void SeqList_Destory(SeqList *list);        /* 销毁顺序表 */
void SeqList_Clear(SeqList *list);          /* 清空顺序表 */
int SeqList_Length(SeqList *list);          /* 获取顺序表长度 */
int SeqList_Capacity(SeqList *list);        /* 获取顺序表容量 */
/* 在pos位置插入元素 */
int SeqList_Insert(SeqList *list,SeqListNode *node,int pos);    
/* 获取pos位置的元素 */
SeqList *SeqList_Get(SeqList *list,int pos);    
/* 删除pos位置的元素 */
SeqList *SeqList_Delete(SeqList *list, int pos);
#endif

顺序存储链表实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "SeqList.h"
/* 创建顺序表,返回值为SeqList*类型,即顺序表的地址 */
SeqList *SeqList_Create(int capacity)   
{
    int ret;
    TSeqList *temp=NULL;
    temp=(TSeqList*)malloc(sizeof(TSeqList)); /* 为头节点分配地址 */
    if(temp==NULL)
    {
        ret=1;
        printf("func SeqList_Create() error:%d\n",ret);
        return NULL;
    }
    memset(temp, 0, sizeof(TSeqList));
    temp->capacity=capacity;
    temp->length=0;
    /* 分配一个指针数组 char**malloc(sizeof(char*)*capacity) */
    temp->node=(int*)malloc(sizeof(void*)*capacity);    
    if(temp->node==NULL)
    {
        ret=2;
        printf("func SeqList_Create() error:%d\n",ret);
        return NULL;
    }
    return temp;
}

int SeqList_Capacity(SeqList *list) /* 求顺序表容量 */
{
    TSeqList *temp=NULL;
    if(list==NULL)
    {
        return;
    }
    temp=(TSeqList *)list;
    return temp->capacity;
}

int SeqList_Length(SeqList *list) /* 获取顺序表长度 */
{
    TSeqList *temp=NULL;
    if(list==NULL)
    {
        return;
    }
    temp=(TSeqList *)list;
    return temp->length;
}
/* 插入元素 */
int SeqList_Insert(SeqList *list,SeqListNode *node,int pos)
{
    int i;
    TSeqList *temp=NULL;
    if(list==NULL || node==NULL)    /* 健壮性判断 */
    {
        return -1;
    }
    temp=(TSeqList *)list;
    if(temp->length >= temp->capacity)  /* 如果顺序表已满 */
    {
        return -2;
    }
    /* 如果给出的pos位置在线性表长度之后,即中间有空余 */
    if(pos >temp->length)       
    {
        pos=temp->length;       /* 就修正到最后一个元素后面 */
    }
    /* 将插入元素后的元素依次后移 */
    for(i=temp->length;i>pos;i--)   
    {
        temp->node[i]=temp->node[i-1];
    }
    /* 腾出的位置插入新元素 */
    temp->node[i]=(SeqListNode *)node; 
    temp->length++;             /* 插入成功后,长度加1 */
    return 0;
}

SeqList *SeqList_Delete(SeqList *list, int pos) /* 删除元素 */
{
    int i;
    TSeqList *tlist=NULL;
    SeqListNode *temp=NULL;
    tlist=(TSeqList*)list;
    if(list==NULL || pos<0 || pos>=tlist->capacity)
    {
        printf("SeqList_Detele() error\n");
        return NULL;
    }
    temp=(SeqListNode*)tlist->node[pos];    /* 要删除的元素 */
    for(i=pos+1;i<tlist->length;i++)
    {
        tlist->node[i-1]=tlist->node[i];
    }
    tlist->length--;
    return temp;
}

SeqList *SeqList_Get(SeqList *list, int pos) /* 查找元素 */
{
    TSeqList *tlist=NULL;
    SeqListNode *temp=NULL;
    tlist=(TSeqList *)list;
    if(list==NULL || pos<0 || pos>=tlist->capacity)
    {
        printf("SeqList_Get() error\n");
        return NULL;
    }
    /* 将表中pos位置的结点指针赋给temp */
    temp=(SeqListNode *)tlist->node[pos];   
    return temp;
}

void SeqList_Clear(SeqList *list)  /* 清空顺序表 */
{
    TSeqList *temp=NULL;
    if(list==NULL)
    {
        return;
    }
    temp=(SeqList*)list;
    temp->length=0;
    memset(temp->node, 0, (temp->capacity*sizeof(void*)));
    return;
}

void SeqList_Destory(SeqList *list) /* 销毁顺序表 */
{
    TSeqList *temp=NULL;
    if(list==NULL)
    {
        return;
    }
    temp=(TSeqList *)list;
    if(temp->node != NULL)
    {
        free(temp->node);   /* 先释放头节点中的指针数组 */
    }
    free(temp);     /* 在释放头节点 */
    return;
}

Unit Test

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "SeqList.h"

typedef struct _Teacher
{
    char name[32];
    int age;
}Teacher;

int main()
{
    int ret =0;
    int len =0;
    int i       =0;

    SeqList *list=NULL;
    Teacher t1={
        "loci",
        32
    };
    Teacher t2={
        "coco",
        23
    };
    Teacher t3={
        "lili",
        21
    };
    Teacher t4={
        "fgfg",
        45
    };
    Teacher t5={
        "ktkt",
        28
    };

    /* 创建顺序表 */
    list=SeqList_Create(10);

    /* 头插法 */
    ret=SeqList_Insert(list,(SeqListNode*)&t1,0);   
    ret=SeqList_Insert(list,(SeqListNode*)&t2,0);
    ret=SeqList_Insert(list,(SeqListNode*)&t3,0);
    ret=SeqList_Insert(list,(SeqListNode*)&t4,0);
    ret=SeqList_Insert(list,(SeqListNode*)&t5,0);

    printf("顺序表容量:%d\n",SeqList_Capacity(list));
    printf("顺序表长度:%d\n",SeqList_Length(list));
    len=SeqList_Length(list);

    printf("遍历顺序表:\n");
    for(i=0;i<len; i++)
    {
        Teacher *temp=(Teacher *)SeqList_Get(list,i);   
        if(temp==NULL)
        {
            printf("func SeqList_Get() error\n");
            return;
        }
        printf("teachr name:%s\tage:%d\n",temp->name,temp->age);
    }

    printf("销毁顺序表:\n");
    while(SeqList_Length(list)>0)
    {
        /* 删除头部元素 */
        Teacher *temp=(Teacher *)SeqList_Delete(list,0);    
        if(temp==NULL)
        {
            printf("func SeqList_Delete error\n");
            return;
        }
        printf("teachr name:%s\tage:%d\n",temp->name,temp->age);
    }
    SeqList_Destory(list);
    system("pause");
    return 0;
}