目录
单链表结构
将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块， 称为结点， 通过地址或指针建立它们之间的联系， 所得到的存储结构为链表结构。
其中， 结点的data域存放数据元素ai， 而next域是一个指针， 指向ai的直接后继ai+1所在的结点。 于是， 线性表L=( a0,a1,……,an-1)的结构如图
线性表的链式存储结构
typedef int data_t;
typedef struct node{
data_t data;
struct node* next;
}listnode,*listlink;
//创建链表
listlink list_creat();
//尾插入
int list_insert(listlink H,data_t value);
//打印链表
int list_show(listlink H);
//任意节点插入
int list_insert_head(listlink H,data_t value,int pos);
//某节点是否存在元素
listlink list_get(listlink H,int pos);
//删除某节点
int list_delete(listlink H,int pos);
//删除链表
listlink list_free(listlink H);
//链表从小到达排序
listlink list_sort(listlink H);
//查询某元素是否存在
int list_key(listlink H,int num);
//元素反转
int list_reverse(linklist H);
//合并有序链表
linklist list_adjmax(linklist H, data_t *value);
链式存储实现
链表创建
listlink list_creat(){
//申请内存
listlink H;
H = (listlink)malloc(sizeof(listnode));
if (NULL==H){
printf("malloc is error!\n");
}
//初始化赋值
H->data=0;
H->next=NULL;
//返回
return H;
}创建同时赋值
linklist list_create()
{
//申请内存
linklist H,r,p;
int value;
if((H=(linklist)malloc(sizeof(listnode)))==NULL)
{
printf("malloc failed!\n");
return H;
}//初始化
H->data = 0;
H->next = NULL;
r=H;
//用户在创建的同时并给后面节点赋值，输入-1结束
while(1)
{
printf("input a number(-1 exit):");
scanf("%d",&value);
if(value == -1)
break;
if((p=(linklist)malloc(sizeof(listnode)))==NULL)
{
printf("malloc failed\n");
return H;
}
p->data = value;
p->next = NULL;
r->next = p;
r=p;
}
return H;
}尾结点插入
int list_insert(listlink H,data_t value){
if(H == NULL){
printf("H is NULL");
return -1;
}
//申请内存
listlink p;
listlink q=H;
if((p=(listlink)malloc(sizeof(H)))==NULL){
printf("malloc is fail\n");
return -1;
}
p -> next = NULL;
p->data = value;
//找尾节点
while(q->next!=NULL){
q = q->next;
}
//赋值,把P的地址放到前一个节点的next处
q->next = p;
return 0;
}
任意节点插入
int list_insert_head(listlink H,data_t value,int pos){
if(H == NULL){
printf("H is NULL\n");
return -1;
}
listlink p ,q;
//申请新的节点空间
q = (listlink)malloc(sizeof(H));
if(q==NULL){
printf("malloc error\n");
return -1;
}
//判断插入的前一个节点是否存在，pos是否正常
p = list_get(H,pos-1);
if(p==NULL||pos<0){
printf("pos is error\n");
return -1;
}
//插入，先链接q的尾部，然后把q的地址给p
q->next = p->next;
q->data = value;
p->next = q;
return 0;
}
获取某位置的地址
listlink list_get(listlink H,int pos){
if(H == NULL){
printf("H is non-existent\n");
return NULL;
}
if(pos==-1){
//printf("H is empty\n");
return H;
}
int head=-1;
listlink p = H;
//遍历到pos处，输出该处的地址
while(head<pos){
p=p->next;
if(p==NULL){
printf("error\n");
return NULL;
}
head++;
}
return p;
}
输出链表元素
int list_show(listlink H){
if(H == NULL){
printf(" list is empty\n");
return -1;
}
listlink p = H;
while(p->next!=NULL){
p = p->next;
printf("%d ",p->data);
}
printf("\n");
return 0;
}
删除某位置节点
int list_delete(listlink H,int pos){
if(H == NULL){
printf("H is NULL\n");
return -1;
}
listlink p ,q;
p = list_get(H,pos);
if(p==NULL||pos<0){
printf("pos is error\n");
return -1;
}
//获取pos之前的节点地址
q = list_get(H,pos-1);
q->next = p->next;
free(p);
p = NULL;
return 0;
}
删除链表
listlink list_free(listlink H){
listlink p;
p = H;
while(H!=NULL){
H = p->next;
printf("%d ",p->data);
free(p);
p = H;
/*p = H;
printf("%d ",p->data);
H = H->next;
free(p);*/
}
puts("\n");
return NULL;
}
返回某元素位置
int list_key(listlink H,int num){
listlink p = H->next;
int n=0;
while(p!=NULL){
if(num == p->data){
return n;
}
n++;
p = p->next;
}
return n;
}
对链表元素冒泡排序
listlink list_sort(listlink H){
if(H == NULL){
printf("H is NULL\n");
return NULL;
}
if(H->next == NULL||H->next->next == NULL){
printf("H is empty\n");
return H;
}
listlink p = H->next,q,w;
q = p;
w = H->next;
int a=0,i=0;
while(w!=NULL){
w = w->next;
a++;
}
printf("%d\n",a);
while(i<a){
int num ;
while(p->next!=NULL){
p = p->next;
if(p->data <q->data ){
num = p->data;
p->data = q->data;
q->data = num;
}
//list_show(H);
q = q->next;
}
q=H;
p=H;
i++;
}
return H;
}
对链表元素排序
listlink list_sort(listlink H){
listlink p,q,r;
//int t;
if(H == NULL){
printf("H is NULL");
return NULL;
}
p = H->next;
H->next = NULL;
r = H;
while(p != NULL)
{
q = p;
p = p->next;
r = H;
//判断q节点值是否大于第一个节点值，如果大于，r后移，一直到小于q的值
while(r->next && r->next->data < q->data){
r = r->next;
}
//替换比q小的值
q->next = r->next;
r->next = q;
}
return H;
}