数据结构】2.22试写一算法,对单链表实现就地逆置"/>
【数据结构】2.22试写一算法,对单链表实现就地逆置
【数据结构】2.22试写一算法,对单链表实现就地逆置
转载-就地逆转单链表和在单链表结构上实现线性表操作Locate(L,x).
``
//就地逆转单链表和在单链表结构上实现线性表操作Locate(L,x)
#include <iostream>
using namespace std;
#include <malloc.h>
#include <stdio.h>
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define IINFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 10
#define LISTINCREAMENT 2typedef int ElemType;
typedef int Status;typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
void CreateList_L(LinkList &L,int n){//逆位序输入n个元素的值,建立带头结点的单链表Lint i;LinkList p;L=(LinkList)malloc(sizeof(LNode));L->next = NULL;//先建立一个带头结点的单链表for(i = n;i>0;--i){p = (LinkList)malloc(sizeof(LNode)); //生成新结点scanf("%d",&p->data); //插入元素值p->next = L->next;L->next = p;//插入到表头}//CreateList_L}
void PrintList_L(LinkList L){//打印输出链表元素的值LinkList p=L->next;while(p){printf("%d ",p->data);p = p->next;}printf("\n");
}//PrintList_L
Status GetElem_L(LinkList L,int i,ElemType &e){//L为带头结点的单链表的头指针//当第i个元素存在时,其赋值给e并返回OK,否则返回ERRORLinkList p;p=L->next;int j=1; //初始化,p指向第一个结点,j为计数器while(p&&j<i){//顺时针向后查找,直到P指向第i个元素或p为空p=p->next;++j;}if(!p||j>i)return ERROR; //第i个元素不存在e=p->data; //取第i个元素return OK;
}//GetElem_LStatus LinkInsert_L(LinkList &L,int i,ElemType e){//在带头结点的单链线性表L中第i个位置之前插入元素eLinkList p;LinkList s;p=L;int j=0;while(p&&j<i-1){ //寻找第i-1个结点p=p->next;++j;}if(!p||j>i-1)//i小于1或者大于表长加1return ERROR;s=(LinkList)malloc(sizeof(LNode)); //生成新结点s->data=e;s->next=p->next; //插入L中p->next=s;return OK;
}//LinkInsert_L
Status LinkDelete_L(LinkList &L,int i,ElemType &e){//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值LinkList p;LinkList q;p=L;int j=0;while(p->next&&j<i-1){ //寻找第i个结点,并令p指向其前驱p=p->next;++j;}if(!(p->next)||j>i-1)return ERROR; //删除位置不合理q=p->next;p->next=q->next; //删除并释放结点e=q->data;free(q);
}//LinkDelete_L
Status ConverseList(LinkList &L)
{LinkList p,q,r;p=L->next;//p指向第一个结点q=p->next;//q指向第二个结点p->next=NULL;//并将p作为尾结点while(q){r=q->next;//r指向q的下一个结点q->next=p;//并将p赋值给q->nextp=q;q=r;//进行右移操作}L->next=p;return OK;}
int LocateElem(LinkList L,ElemType x)
{int i=0;LinkList p=L;while(p&&p->data!=x){p=p->next;i++;}if(!p)return 0;elsereturn i;
}
int main()
{struct LNode;ElemType e;LinkList L;int i,n,t,a,b,x;printf("请输入链表中最开始的数据个数\n");scanf("%d",&n);printf("请输入链表中最开始的数据\n");CreateList_L(L,n);printf("目前表中元素为:\n");PrintList_L(L);printf("请输入需要插入元素的位置:");scanf("%d",&i);printf("请输入需要插入元素的的值:");scanf("%d",&e);t=LinkInsert_L(L,i,e);if(t==OK){printf("插入成功!");printf("插入成功后的链表中元素为:\n");PrintList_L(L);}else{printf("插入失败!");}printf("请输入需要得到指定元素的位置:\n");scanf("%d",&i);a=GetElem_L(L, i,e);if(a==OK){printf("得到成功!");printf("得到成功后的元素为%d\n",e);}else{printf("得到失败!");}printf("请输入需要删除元素的位置:\n");scanf("%d",&i);b=LinkDelete_L(L,i,e);if(b==OK){printf("删除成功!");printf("删除的元素为%d\n",e);printf("删除成功后的链表元素为:\n");PrintList_L(L);}else{printf("删除失败!\n");}printf("就地转置单链表:\n");ConverseList(L);PrintList_L(L);printf("请输入需要查找的元素:\n");scanf("%d",&x);LocateElem(L,x);printf("查找的元素在第%d个位置",i);return 0;
}
更多推荐
【数据结构】2.22试写一算法,对单链表实现就地逆置
发布评论