链表操作，时间复杂度为O（n),重在思维和设计，如下给出了一个链表的常见操作的实例
(1) 维护一个数组，来标记链表的元素是否存在
(2)数组下标和值得反应反映射，例如 a ={10,20,30,20}
t[256] = {-1}
t[10] =1;t[20] =1;t[30] =1;
a数组的最后一个元素为20,t[20]已经为1，记录20存在元素的个数，t[20]++;即可
/************************************************************************* > File Name: list_op.h
> Author: zhoulin
> Mail: 715169549@qq.com
> Created Time: Sat 23 Apr 2016 09:23:40 AM CST
************************************************************************/
#ifndef _LIST_OP_H
#define listSize 256
#include <pthread.h>
typedef struct _listNode
{
int v;
struct _listNode *next;
}listNode;
typedef struct _listMgr
{
unsigned int len;
int vmax;
int vmin;
struct _listNode *head;
int flag[listSize];
pthread_mutex_t lock;
}listMgr;
#define listMgrInit(mgr,max) \
{ \
mgr->len = 0; \
mgr->vmax = max; \
mgr->vmin = max; \
mgr->head = NULL; \
memset(mgr->flag,-1,sizeof(int)*max); \
}
#define rebuild(p,h,t) \
{ \
if(h == NULL) \
{ \
h = t = p; \
}else{ \
t->next = p; \
t = p; \
} \
t->next = NULL; \
}
//打印链表，时间复杂度O(n)
void listPrt(listNode *p);
//链表初始化，时间负责度O(n)
listNode *listInit(listMgr *mgr,listNode *a,int n,int max);
//删除链表P中有过重复的元素
listNode *listDRepeat(listMgr *mgr);
//删除链表中重复元素
listNode *listNRepeat(listMgr *mgr);
//给定一个值，要求链表左边小于该值,链表右边大于该值，且链表的相对位置不改变
listNode *listQuick(listMgr *mgr,int v);
//链表排序
listNode *listOrder(listMgr *mgr);
#define _LIST_OP_H
#endif
/*************************************************************************
> File Name: list_op.c
> Author: zhoulin
> Mail: 715169549@qq.com
> Created Time: Sat 23 Apr 2016 09:15:55 AM CST
************************************************************************/
#include "list_op.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
listNode *listQuick(listMgr *mgr,int v)
{
pthread_mutex_init(&mgr->lock,NULL);
pthread_mutex_lock(&mgr->lock);
fprintf(stdout,"**************************v=%d,大于v的节点在v节点右侧，否则在左侧*****************************\n",v);
listNode *b_h,*b_t;
listNode *s_h,*s_t;
listNode *r_h,*r_t;
int *flag = mgr->flag;
if(flag[v] <= 0)
{
return mgr->head;
}
r_h = r_t = b_h = b_t = s_h = s_t=NULL;
listNode *p = mgr->head;
while(p != NULL)
{
listNode *pnext = p->next;
if(p->v == v)
{
rebuild(p,r_h,r_t);
}
else if(p->v > v)
{
rebuild(p,b_h,b_t);
}else{
rebuild(p,s_h,s_t);
}
p = pnext;
}
if(s_t != NULL)
mgr->head = s_h;
s_t->next = r_h;
if(r_t != NULL)
r_t->next = b_h;
pthread_mutex_unlock(&mgr->lock);
return mgr->head;
}
listNode *listNRepeat(listMgr *mgr)
{
pthread_mutex_init(&mgr->lock,NULL);
pthread_mutex_lock(&mgr->lock);
fprintf(stdout,"------------------------->删除链表重复元素<-----------------------------\n");
listNode *cur = mgr->head;
listNode *head = NULL;
int *flag = mgr->flag,i = 0;
mgr->len = 0;
while(cur != NULL && i >= 0)
{
listNode *pnext = cur->next;
if(i == 0){
mgr->vmax = cur->v;
mgr->head = head = cur;
mgr->len++;
}else
{
if(flag[cur->v] >= 1){
head->next = cur;
head = cur;
flag[cur->v] = -1;
if(i != 0){
if(mgr->vmax <= cur->v) mgr->vmax = cur->v;
if(mgr->vmin >= cur->v) mgr->vmin = cur->v;
}
mgr->len++;
}
}
i++;
cur = pnext;
}
pthread_mutex_unlock(&mgr->lock);
return mgr->head;
}
listNode *listDRepeat(listMgr *mgr)
{
pthread_mutex_init(&mgr->lock,NULL);
pthread_mutex_lock(&mgr->lock);
fprintf(stdout,"*************************删除链表有重复元素*****************************\n");
int i = 0;
listNode *p = mgr->head;
listNode *head,*tail;
head = tail = NULL;
mgr->len = 0;
int *flag = mgr->flag;
while(p != NULL)
{
listNode *next = p->next;
if(flag[p->v] == 1)
{
if(head == NULL)
{
mgr->head = head = tail = p;
mgr->vmax = p->v;
}
else{
if(mgr->vmax <= p->v){
mgr->vmax = p->v;
}
if(mgr->vmin >= p->v){
mgr->vmin = p->v;
}
tail->next = p;
tail = p;
}
tail->next = NULL;
mgr->len++;
}
p = next;
}
pthread_mutex_unlock(&mgr->lock);
return mgr->head;
}
listNode *listInit(listMgr *mgr,listNode *a,int n,int max)
{
if(n <= 0)
{
return NULL;
}
if(n > max)
{
n = max;
}
int i = 0;
pthread_mutex_init(&mgr->lock,NULL);
pthread_mutex_lock(&mgr->lock);
listMgrInit(mgr,max);
int *flag = mgr->flag;
fprintf(stdout,"**************************原始链表*****************************\n");
for(i = 0;i < n;i++)
{
a[i].v = rand()%max;
if(flag[a[i].v] == -1)
{
flag[a[i].v] = 1;
}else{
flag[a[i].v]++;
}
if(i == 0){
mgr->vmax = a[i].v;
mgr->vmin = a[i].v;
}else{
if(mgr->vmax <= a[i].v){
mgr->vmax = a[i].v;
}
if(mgr->vmin >= a[i].v){
mgr->vmin = a[i].v;
}
}
listNode *cur = &a[i];
if(i == n -1){
a[i].next = NULL;
fprintf(stdout,"%d\n",cur->v);
break;
}
a[i].next = &a[i+1];
fprintf(stdout,"%d ->",cur->v);
}
mgr->len = n;
mgr->head = a;
fprintf(stdout,"\nhead->v =%d,len=%d,max =%d,vmin=%d\n",mgr->head->v,mgr->len,mgr->vmax,mgr->vmin);
fprintf(stdout,"\n");
pthread_mutex_unlock(&mgr->lock);
return a;
}
void listPrt(listNode *p)
{
listNode *cur = p;
while(cur != NULL)
{
if(cur->next == NULL)
{
fprintf(stdout,"%d\n\n",cur->v);
break;
}
fprintf(stdout,"%d ->",cur->v);
cur = cur->next;
}
}
listNode *listOrder(listMgr *mgr)
{
pthread_mutex_init(&mgr->lock,NULL);
pthread_mutex_lock(&mgr->lock);
fprintf(stdout,"----------------->链表排序<------------------------------------\n");
listNode *cur = mgr->head;
int max = mgr->vmax;
int i = mgr->vmin;
int *flag = mgr->flag;
listNode *head,*tail;
head = tail = NULL;
for(;i <= max;i++)
{
if(flag[i] >0 && cur != NULL)
{
cur->v = i;
listNode *n = cur->next;
if(head == NULL) mgr->head = head = tail = cur;
else {
tail->next = cur;
tail = cur;
}
tail->next = NULL;
flag[i--]--;
cur = n;
}
else
continue;
}
pthread_mutex_unlock(&mgr->lock);
return mgr->head;
}
int main(void)
{
listNode a[listSize];
listNode *tmp = NULL;
listMgr mgr;
listNode *ai = listInit(&mgr,&a[0],56,17);
mgr.head = ai;
tmp = listQuick(&mgr,rand()%10-1);
listPrt(tmp);
fprintf(stdout,"head->v =%d,len=%d,max =%d,vmin=%d\n\n",mgr.head->v,mgr.len,mgr.vmax,mgr.vmin);
ai = listInit(&mgr,&a[0],56,17);
tmp = listNRepeat(&mgr);
listPrt(tmp);
fprintf(stdout,"head->v =%d,len=%d,max =%d,vmin=%d\n\n",mgr.head->v,mgr.len,mgr.vmax,mgr.vmin);
ai = listInit(&mgr,&a[0],56,17);
tmp = listDRepeat(&mgr);
listPrt(tmp);
fprintf(stdout,"head->v =%d,len=%d,max =%d,vmin=%d\n\n",mgr.head->v,mgr.len,mgr.vmax,mgr.vmin);
ai= listInit(&mgr,&a[0],56,17);
tmp = listOrder(&mgr);
listPrt(tmp);
fprintf(stdout,"head->v =%d,len=%d,max =%d,vmin=%d\n\n",mgr.head->v,mgr.len,mgr.vmax,mgr.vmin);
return 0;
}
运行结果：
zhoulin@:~/code/c_src/algorithm/list_op:./list_op
**************************原始链表*****************************
10 ->15 ->9 ->0 ->15 ->3 ->3 ->14 ->11 ->2 ->5 ->14 ->3 ->2 ->12 ->5 ->11
head->v =10,len=17,max =15,vmin=0
**************************v=5,大于v的节点在v节点右侧，否则在左侧*****************************
0 ->3 ->3 ->2 ->3 ->2 ->5 ->5 ->10 ->15 ->9 ->15 ->14 ->11 ->14 ->12 ->11
head->v =0,len=17,max =15,vmin=0
**************************原始链表*****************************
6 ->14 ->1 ->8 ->2 ->5 ->14 ->5 ->8 ->4 ->14 ->11 ->0 ->15 ->10 ->0 ->6
head->v =6,len=17,max =15,vmin=0
------------------------->删除链表重复元素<-----------------------------
6 ->14 ->1 ->8 ->2 ->5 ->4 ->11 ->0 ->15 ->10 ->6
head->v =6,len=12,max =15,vmin=0
**************************原始链表*****************************
16 ->3 ->10 ->4 ->14 ->3 ->9 ->2 ->6 ->2 ->6 ->3 ->13 ->10 ->9 ->2 ->11
head->v =16,len=17,max =16,vmin=2
*************************删除链表有重复元素*****************************
16 ->4 ->14 ->13 ->11
head->v =16,len=5,max =16,vmin=2
**************************原始链表*****************************
9 ->4 ->0 ->6 ->0 ->16 ->10 ->5 ->10 ->10 ->4 ->3 ->2 ->1 ->10 ->5 ->2
head->v =9,len=17,max =16,vmin=0
----------------->链表排序<------------------------------------
0 ->0 ->1 ->2 ->2 ->3 ->4 ->4 ->5 ->5 ->6 ->9 ->10 ->10 ->10 ->10 ->16
head->v =0,len=17,max =16,vmin=0