线性表 | Tree's Blog

线性表的基本操作

顺序表定义

typedef int DataType;
struct List
{
    int Max;//最大元素个数
    int n;//实际元素个数
    DataType *elem;//首地址
};
typedef struct List *SeqList;//顺序表类型定义

顺序表遍历

void Print(SeqList slist)
{
    int i;
    for(i=0;i<slist->n;i++)
        printf("%d\n",slist->elem[i]);
}

创建空顺序表

SeqList SetNullList_Seq(int m)//m为顺序表最大值
{
    SeqList slist=(SeqList)malloc(sizeof(struct List)*m);//申请结构体空间
    if(slist!=NULL)
    {
        slist->elem=(DataType *)malloc(sizeof(int)*m);//申请顺序表空间，大小为m个int空间
        if(slist->elem)
        {
            slist->Max=m;
            slist->n=0;
           return(slist); 
        }
        else free(slist);
        
    }
    printf("Alloc failure!\n");
    return NULL;

}

判断顺序表为空

int IsNullList_Seq(SeqList slist)
{
    return(slist->n==0);
}

顺序表–插入

int InserPre_seq(SeqList slist,int p,DataType x)//在线性表slist的p之前插入x,如果成功返回1，不成功返回0；
{
    int q;
    if(slist->n=slist->Max)
    {
        printf("overflow");
        return 0;
    }
    if(p<0||p>slist->n)
    {
        printf("not exist!\n");
        rerurn 0;
    }
    for(q=slist->n-1;q>=p;q--)
        slist->elem[q+1]=slist->elem[q];
     slist->elem[p]=x;
     slist->n=slist->n+1;
     return 1;
    
}

顺序表–删除

int DdlIdex_seq(SeqList slist,int p)//删除下标为p的元素
{
    int q;
    if(q<0||q>slist->Max)
    {
        printf("Not exist\n");
        return 0;
    }
    for(q=p;q<slist->n-1;q++)
        slist->elem[q]=slist->elem[q+1]；
    slist->n=slist->n-1;
    return 1;
}

顺序表–查找

int LocateIndex_seq(SeqList slist,int x)//查找值为x的元素，返回元素的下标
{
    int q;
    for(q=0;q<slist->n;q++)
    {
        if(slist->elem[q]==x)
            return q;
    }
    return -1;
    
}

顺序表–二分查找–非递归

int Binsearch(SeqList slist,int key,int *pos)
{
    int index=1;//比较次数
    int mid;
    int low=0;
    int high=slist->n-1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(slist->elem[mid]==key)
        {
            *pos=mid;
            printf("找到，共进行%d次比较\n",index);
            printf("要找到的数据%d在位置%d上\n",key,mid);
            return 1;
        }
        else if(slist->elem[mid]>key)
            high=mid-1;
            else
                low=mid+1;
        index++;
    }
    *pos=low;
    printf("没有找到，共比较%d次\n",index-1);
    printf("可将此数据插入到位置%d上\n",*pos);
    return -1;
}

顺序表–二分查找–递归

int Binsearch_recursion(SeqList slist,int key,int low,int high,int *pos)
{
    int mid;
    if(low<=hight)
    {
        mid=(low+high)/2;
        if(slist->elem[mid]==key)
        {
            printf("要找的数据%d在位置%d上",key,mid);
            return 1;
        }
        if(slist->elem[mid]>key)
        {
            *pos=mid;
            return Binsearch_recursion(slist,key,low,mid-1,pos);
            if(slist->elem[mid]<key)
            {
                *pos=mid+1;
            return Binsearch_recursion(slist,key,mid+1,high,pos+1);
            }
        }
    }
    printf("没有找到，可将此数插入到位置%d上\n",*pos);
    return -1;
}

链表定义

typedef int DataType;
struct Node
{
    DataType data; //数据域
    struct Node *next;//指针域
};
typedef struct Node *PNode;//节点类型定义
typedef struct Node *LinkList;//单链表类型定义

链表遍历

void Print(LinkList head)
{
    PNode p=head->next;
    while(p)
    {
        printf("%d\n",p->data);
        p=p->next;
    }
}

创建单链表

LinkList SetNullList_List()
{
    LinkList head=(LinkList)malloc(sizeof(struct Node));
    if(head!=NULL)
        head->next=NULL;
    else
        printf("Alloc faliure");
    return head;
}

判断链表为空

int IsNull_List(Linklist head)
{
    return(head->next==NULL);
}

头插法建立单链表

void CreateList_Head(struct Node *head)
{
    PNode p=NULL;
    int data;
    printf("请输入整型数据建立链表，以-1结束\n");
    scanf("%d",&data);
    while(data!=-1)
    {
        p=(struct Node)malloc(sizeof(struct Node));
        p->data=data;
        p->next=head->next;
        head->head=p;
        scanf("%d",&data); 
    }
}

尾插法建立单链表

void CreateList_Tail(struct Node *head)
{
    PNode p=NULL;
    PNode q=head;
    int data;
    printf("请输入整型数据建立链表，以-1结束\n");
    scanf("%d",&data);
    while(data!=1)
    {
        p=(struct Node)malloc(sizeof(struct Node));
        p->data=data;
        p->next=NULL;
        q->next=p;
        q=p;
        scanf("%d",&data);
    }
}

单链表的查找

PNode Locate_Link(LinkList list,DataType x)
{
    PNode p;
    if(llist==NULL) return NULL;
    p=llist->next;
    while(p!=NULL&&p->data!=x)
        p=p->next;
    return p;
}

单链表的插入–后插算法

int InsertPost_Link(LinkList llist,PNode p,DataType x)//在llist链表中的p位置之后插入值为x的结点
{
    PNode q;
    if(p==NUll)
    {
        printf("para meter failure!\n");
        return 0;
    }
    q=(PNode)malloc(sizeof(struct Node));
    if(q==NULL)
    {
        printf("Alloc failure!\n");
        return 0;
    }
    else
    {
        q->data=x;
        q->next=p->next;
        p->next=q;
        return 1;
    }
}

单链表的插入–前插算法

int InsertPre_Link(LinkList llist,PNode p,DataType x)//在llist链表中的p位置之前插入值为x的结点
{
    PNode q=NULL;
    PNode pre=llist;
    while(pre->next!=p)//定位前p的前驱结点
    {
        pre=pre->next;
    }
    q=(PNode)malloc(sizeof(struct Node));
    if(q==NULL)return 0;
    q->data=x;
    q->next=p;
    pre->next=q;
    return 1;
}

单链表按位删除

void DelPostion_link(LinkList head,PNode r)//删除r指针所指的结点
{
    PNode pre=head;
    while(pre->next!=r)
    {
        pre=pre->next;
    }
    pre->next=r->next;
    free(r);
}

单链表按值删除

void DelValue_Link(struct Node *head,int data)
{
    struct Node *p=head->next;
    struct Node *beforeP=head;
    while(p!=NUll)
    {
        if(p->data==data)
        {
            beforeP->next=p->next;
            free(p);
            break;
        }
        else
        {
            beforeP=p;
            p=p->next;
        }
    }
}