顺序表与单链表基本运算算法

假设表中数据元素的值为整数;

#define    MAX    100    //定义表最大长度容量,实际用不到那么多

//顺序表结构定义

typedef    struct 

{

    int        data[MAX];     //存放表结点

    int        length;        //当前表长度

} SeqList;

//创建初始顺序表

SeqList    *createList(int size)

{

    int    i;

    SeqList    *list;

list=(SeqList *)malloc(sizeof(SeqList));  //分配空间

    printf("请输入顺序表中的整数,元素个数为%d\\n",size);

for(i=0;i scanf("%d",&list->data[i]) ; //逐一向顺序表中输入元素

list->length=size; //顺序表的长度赋值

    return    list;

}

//打印顺序表中的现有元素

printList(SeqList *list)

{

    int    i;

    printf("\\n目前顺序表中有%d个元素\n", list->length);

    printf("这些元素分别是：\n");

for(i=0;ilength;i++)

printf("%d ",list->data[i]); //依次打印输出顺序表中的元素

    printf("\\n");

}

//在顺序表中查找值为e的元素,并返回它在表中的位置

Int locate(SeqList *list, int e)

{

    int    i=0;

    while(ilength && list->data[i]!=e)

i++ ;   //依次比较顺序表中各个元素

if(ilength) return i+1;             //找到元素的处理

    else        printf("找不到元素!\n",);       //未找到元素的处理

}

//在表中第i个元素之前插入新元素e

insert(SeqList *list, int i , int e)

{

      int j;

if (i<1 || i>list->length+1 ) //检查插入位置的合法性

printf("插入位置非法！不能插入\n！"); 

     else if (list->length==MAX)

printf("表满，不能插入！\n"); //检查表空满情况

     else {for(j=list->length-1;j>=i-1;j--)

     list->data[j+1]=list->data[j];

//从第n个元素开始到第i个元素依次向后移动一个位置

                 list->data[i-1]=e; //新元素e插入i位置

                 list->length++;         //表长加1

                     }

    }

//删除表中第i个元素

delete(SeqList *list, int i)

{

    int    j;

if (i<1 || i>list->length ) printf("删除位置非法！不能删除！\n"); 

//检查删除位置的合法性

    else if (list->length==0) printf("表空，不能删除！\n");                       //检查表空满情况

         else 

     {for(j=i;j<=list->length;j++)

         list->data[j-1]=list->data[j];                    

//从第i个元素开始到第n个元素依次向前移动一个位置

     list->length--;      //表长减1

         }

}

单链表的基本运算实现

以下算法都是带头结点的算法;

假设表中数据元素的值为整数;

//链表结点结构定义

typedef    struct node

{

    int        data;     //存放表结点值

    struct node *next;   //存放表结点的直接后驱元素的地址

} ListNode,*LinkList;

//头插法创建初始链表

LinkList create_h(int size)

{

   LinkList head,p;

   int i;

head=(LinkList)malloc(sizeof(ListNode));//申请头结点的存储空间

head->next=Null;//头结点的next域为Null

printf("请输入这%d个元素的值:\\n",size);

for(i=0;i   {

       p=(LinkList)malloc(sizeof(ListNode));

scanf("%d",&p->data);

p->next=head->next;

head->next=p;

   }

   return head;   

}

//尾插法创建初始链表

LinkList create_t(int size)

{

   LinkList head,p,r;

   int i;

head=(LinkList)malloc(sizeof(ListNode)); //申请头结点的存储空间

head->next=Null; //头结点的next域为Null

   r=head;//尾指针指向头结点

   printf("请输入这%d个元素的值:\\n",size);

for(i=0;i   {

       p=(LinkList)malloc(sizeof(ListNode));

scanf("%d",&p->data);

p->next=Null;

r->next=p;

       r=p;//尾指针指向新增结点

   }   return head;     }

//求链表的长度

int length(LinkList head)

{

    LinkList p;

    int i;

p=head->next;//工作指针指向表中第一个结点

    i=0;//计数器置0

    while(p!=Null)

    {

        i++;//计数器计数

        p=p->next;//工作指针后移到下一个结点

    }

    return i;

}

//打印链表中的现有元素

printList(LinkList head)

{

    LinkList p;

p=head->next;//工作指针指向表中第一个结点

    while(p!=Null)

    {

     printf("%d ",p->data);//打印当前指针所指结点的值

        p=p->next;//工作指针后移到下一个结点

    }

}

//按位查找元素

DataType get(LinkList head ,int i)

{

    LinkList p;

    int j;

    p=head->next; //工作指针指向表中第一个结点

    j=1; //计数器置1

    while(p!=Null && j    {

        p=p->next;

        j++;

    }

    if(p!=Null && j==i) return p->data;//查找成功,p指向第i个结点,返回第i个结点值

    else return Null;//i值非法,查找失败

}

//按值查找元素

LinkList locate(LinkList head,int x)

{

    LinkList p;

    p=head->next;

while(p!=Null && p->data!=x)

        p=p->next;

if (p!=Null && p->data==x)

        {printf("找到该元素!”);return p;}

    else

        {printf("找不到该元素!\\n");return Null;}

}

//在链表中第i个元素前插入新元素

insert(LinkList head,int i,int x)

{

    LinkList p,s;

    int j;

    p=head;//工作指针指向头结点,方便在第1个结点之前插入新元素

    j=0;//计数器置0

    while(p!=Null && j    {

        p=p->next;

        j++;

    }

    if (p!=Null && j==i-1)//定位成功

    {

        s=(LinkList)malloc(sizeof(ListNode));//申请新结点存储空间

        s->data=x;

     s->next=p->next;//新结点插入

        p->next=s;//新结点插入

    }

    Else//插入位置非法

        printf("插入位置非法！\n");

}

//在链表中删除第i个结点元素

delete(LinkList head,int i)

{

    LinkList p,q;

    int j;

    p=head; //工作指针指向头结点

    j=0; //计数器置0

    while(p->next!=Null && j//将p指针定位到第i个结点的直接前驱接点上;

    { 

        p=p->next;

        j++;

    }

if(p->next!=Null && j==i-1)

    {

     q=p->next;//q指向要被删除的结点

        p->next=q->next;//删除结点

        free(q);//释放已被删除结点的存储空间

    }

    else

        printf("空表或删除位置不合法！\n");

}