线性表和链表

2015.2.4
星期三，多云转晴（出太阳了）
今天上数据结构：链表，下面是我觉得比较好的相关链表程序：

数组：
优点：随机存取；密度高
缺点：插入删除比较麻烦，费时；

线性表的存储结构：

typedef int data_t;

typedef struct node_t{
data_t data;
struct node_t *next;
}linknode_t,*linklist_t;

linknode_t A;
linklist_t P = &A;

线性表的创建，销毁，清空，判空，判满，计算长度，插入一个数，删除一个数，取一个数，替换一个数

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef int data_t;

typedef struct{
data_t data[MAX];
int last;
}seqlist_t, *seqlink_t;

seqlink_t Create_Emptysqlist()
{
seqlink_t list;
list = (seqlink_t)malloc(sizeof(seqlist_t));
if(list)
{
list->last = -1;
}
return list;
}

void Destroy_Sqlist(seqlink_t list)
{
if(list != NULL)
free(list);
}

void Clear_Sqlist(seqlink_t list)
{
if(list)
{
list->last = -1;
}
return;
}

int Empty_Sqlist(seqlink_t list)
{
if(list)
{
if( -1 == list->last)
{
return 1;
}
else
{
return 0;
}
}
else
{
return -1;
}

}

int Full_Sqlist(seqlink_t list)

{
if(list)
{
if(list->last == (MAX - 1))
{
return 1;
}
else
{
return 0;
}
}
else
{
return -1;
}

}

int Length_Sqlist(seqlink_t list)
{
if(list)
{
return (list->last + 1);
}
else
{
return -1;
}

}

int Insert_Sqlist(seqlink_t list,int at,data_t x)
{
int i;
if(list == NULL)
{
return -1;
}

if(Full_Sqlist(list))
{
return -2;
}

if(at > list->last)
{
at = list->last + 1;
}

for(i = list->last; i>=at; i--)
{
list->data[i+1] = list->data[i];
}
list->data[at] = x;
list->last++;

return 0;
}

int Delete_Sqlist(seqlink_t list,int at)
{
int i;
if(list == NULL)
{
return -1;
}
if((at > list->last) || (at < 0))
{
return 0;
}

for(i = at; i < list->last; i++)
{
list->data[i] = list->data[i+1];
}
list->last--;
return 1;
}

int Get_Sqlist(seqlink_t list, int at,data_t *x)
{
if(list == NULL)
{
return -1;
}

if((at > list->last) || (at < 0))
{
return -1;
}
if(x)
{
*x = list->data[at];
}
return 0;

}

int Set_Sqlist(seqlink_t list,int at,data_t x)
{
if(list == NULL)
{
return -1;
}

if((at > list->last) || (at < 0))
{
return -1;
}

list->data[at] = x;

return 0;

}

void iterate_list(seqlink_t list)
{
int i;
printf("list.last = %d, list = {",list->last);

for(i = -1; i < list->last; )
{
printf("%d, ",list->data[++i]);
}

if( Length_Sqlist(list) > 0 )
{
printf("} ");
}
else
{
printf("} ");
}
}

main()
{

int i;
data_t a[] = {2,4,6,8,10,12,14,16,18,20};
data_t x;

seqlink_t list;

list = Create_Emptysqlist();

if(NULL == list)
{
return -1;
}

for(i = 0; i < 10; i++)
{
if(Insert_Sqlist(list,i,a[i]) < 0 )
break;
}

iterate_list(list);
Get_Sqlist(list,4,&x);
printf("list[4] = %d ",x);
printf("updated list[4] to 100 ");
Set_Sqlist(list,4,100);
Get_Sqlist(list,4,&x);
printf("now list[4] = %d ",x);
iterate_list(list);

printf("remove list[4] ");
Delete_Sqlist(list,4);
Get_Sqlist(list,4,&x);
printf("now list[4] = %d ",x);
printf("and total number of list is %d ",Length_Sqlist(list));

iterate_list(list);

Clear_Sqlist(list);
printf("after clear,total number of list is %d ",Length_Sqlist(list));

Destroy_Sqlist(list);

return 0;
}

执行效果：

lg@lg-desktop:/mnt/hgfs/source test/pdf$ gcc list.c
lg@lg-desktop:/mnt/hgfs/source test/pdf$ ./a.out
list.last = 9, list = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20,}
list[4] = 10
updated list[4] to 100
now list[4] = 100
list.last = 9, list = {2, 4, 6, 8, 100, 12, 14, 16, 18, 20,}
remove list[4]
now list[4] = 12
and total number of list is 9
list.last = 8, list = {2, 4, 6, 8, 12, 14, 16, 18, 20,}
after clear,total number of list is 0
lg@lg-desktop:/mnt/hgfs/source test/pdf$

建立单链表：

linklist_t Create_Linklist()
{
data_t a;
linklist_t h, p, r;
h = (linklist_t)malloc(sizeof(linknode_t));
r = h;
scanf("%d",&a);
while(a != -1) //结束符
{
p = (linklist_t)malloc(sizeof(linknode_t));
p->data = a;
r-next = p;
r = p;
scanf("%d",&a);
}

r->next = NULL;
return h;
}
}

链表查找：

linklist_t Get_Linklist(linklist_t h,int i) //第i个节点
{
int j = -1;
linklist_t p = h;
if(i < 0)
{
return NULL;
}

while(p->next && j < i)
{
p = p->next;
j++;
}
if(i == j)
{
return p;
}
else
{
return NULL;
}

}

按值查找：（定位）

linklist_t Locate(linklist_t h, data_t x)
{
linklist_t p = h->next;
while(p && (p->data != x))
{
p = p->next;
}

return p;
}

链表的删除：

int Delete_Linklist(linklist_t h, int i)
{
linklist_t p,q;
if(i == 0)
{
p = h;
}
else
{
p = Get_Linklist(h,i-1);
}

if(p && p->next)
{
q = p->next;
p->next = q-next;
free(p);
return 0;
}
else return -1;
}

链表的插入：

int Insert_Linklist(linklist_h h,data_t x, int i)
{
linklist_t p,q;
if(i == 0)
{
p = h;
}
else
{
p = Get_Linklist(h,i-1);
}
if(p == NULL)
{
return -1;
}
else
{
q = (linklist_t)malloc(sizeof(linknode_t));
q->data = x;
q->next = p->next;
p->next = q;
return 0
}
}

单链表倒置：H->2->4->8 ----》H->8->4->2

void Reverse_Linklist(linklist_t h)
{
linklist_t q,p;
p = h->next;
h->next = NULL;
while(p!=NULL)
{
q = p;
p = p->next;
q->next = h->next;
h->next = q;
}
}

C和指针上面关于链表的最终程序：

单链表的插入：

#include <stdio.h>
#include <stdlib.h>
#include "sll_node.h"

#define FALSE 0
#define TRUE 1

typedef struct NODE{
struct NODE *link;
int value;
}Node;

int sll_insert(register Node **linkp, int new_value)
{
register Node *current;
register Node *new;

while((current = *linkp) != NULL && current->value < new_value)
{
linkp = &current->link;
}

new = (Node *)mallc(sizeof(Node));
if(new == NULL)
{
return FALSE;
}
new->value = new_value;

new->link = current;
*linkp = new;
return TRUE;L
}

C一百题：正向创建链表：

#include <stdio.h>
#include <stdlib.h>

struct list{
int data;
struct list *next;
};

typedef struct list node;
typedef node *link;

void main()
{
link ptr,head;
int num,i;
ptr = (link)malloc(sizeof(node));
head = ptr;
printf("please input 5 numbers ==> ");
for(i = 0; i < 4; i++)
{
scanf("%d",&num);
ptr->data = num;
ptr->next = (link)malloc(sizeof(node));
if(i == 4)
{
ptr->next = NULL;
}
else
{
ptr = ptr->next;
}
}

ptr = head;
while(ptr != NULL)
{
printf("the value is == > %d ",ptr->data);
ptr = ptr->next;
}

}

反向创建链表：

#include <stdio.h>
#include <stdlib.h>

struct list{
int data;
struct list *next;
};

typedef struct list node;
typedef node *link;

void main()
{
link ptr,head,tail;
int num, i;

tail = (link)malloc(sizeof(node));
tail->next = NULL;
ptr = tail;
printf("please input 5 data ==> ");

for(i = 0; i <= 4; i++)
{dd
head = (link)malloc(sizeof(node));
head->next = ptr;
ptr = head;
}

ptr = ptr->next;
while(ptr != NULL)
{
printf("the value is ==> %d ",ptr->data);
ptr = ptr->next;
}
}

双链表的插入：

#include <stdio.h>
#include <stdlib.h>
#include "doubly_liked_list_node.h>

int dll_insert(register *rootp,int value)
{
register Node *this;
register Node *next;
register Node *newnode;

for(this = rootp;(next = this->fwd) != NULL;this = next)
{
if(next->valude == value)
{
return 0;
}
if(next->value > value)
{
break;
}
}

newnode = (Node *)malloc(sizeof(Node));
if(newnode == NULL)
{
return -1;
}
newnode->value = value;

newnode->fwd = next;
this->fwd = newnode;

if(this != rootp)
{
newnode->bwd = this;
}
else
{
newnode->bwd = NULL;
}

if(next != NULL)
{
next-bwd = newnode;
}
else
{
rootp->bwd = newnode;
}
return 1;
}

链表练习：

typedef struct node{
int data;
struct node *link;
}linknode,*linklist_t

linklist_t Create_Linklist()
{
linklist_t list;
list = (linklist_t)malloc(sizeof(linknode));
if(NULL == list)
{
return -1;
}
return list;
}

void Clear_Linklist(linlkist_t list)
{
linklist_t next_node;
if(NULL == list)
{
return;
}
while(NUll != list->next)
{
next_node = list->next;
list->next = next->node->next;
free(next_node);
}
return ;
}

void Destory_Linklist(linklist_t list)
{
if(NULL != list)
{
Clear_Linklist(list);
free(list);
}
}

***************************************************************************************************************************************************************
***************************************************************************************************************************************************************
***************************************************************************************************************************************************************
***************************************************************************************************************************************************************