链表的基本操作 不知道哪里错了 帮忙改下
在单链表存储结构上实现基本操作：初始化、创建、插入、删除、查找、遍历、逆置、合并运算。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 1008
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
using namespace std;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
} SqList;
///初始化
int InitList_Sq(SqList &L)
{
//构造一个空的线性表L
L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
{
exit(0);
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
///线性表的创建和插入
int ListInsert_Sq(SqList &L,int index,ElemType ELEM)
{
ElemType *newbase,*p,*q;
if(1 > index||index > L.length + 1)
{
return ERROR;
}
if(L.length >= L.listsize)
{
newbase = (ElemType*)realloc(L.elem,
(L.listsize + LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
{
exit(0);
}
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[index - 1]);
for(p = &(L.elem[L.length - 1]); p >= q; --p)
{
*(p + 1) = *p;
}
*q = ELEM;
++L.length;
return OK;
}
void Creat_List_Sq(SqList &L,int Length)
{
ElemType ELEM;
int index = 1;
while(index <= Length)
{
scanf("%d",&ELEM);
ListInsert_Sq( L, index, ELEM);
index ++;
}
}
///线性表的输出
void Output_List_Sq(SqList L)
{
int i = 0;
if(L.length == 0)
{
puts("This is a empty List.\n");
}
printf("%d",L.elem[i++]);
while(i < L.length)
{
printf(" %d",L.elem[i++]);
}
printf("\n");
}
///线性表元素删除
int ListDelete_Sq(SqList &L,int index,ElemType &ELEM)
{
ElemType *p,*q;
if(index < 1||index > L.length)
{
exit(0);
}
p = &(L.elem[index - 1]);
ELEM = *p;
q = L.elem + L.length -1;
for(++ p; p <= q; ++ p)
{
*(p - 1) = *p;
}
-- L.length;
return OK;
}
///线性表元素的查找，==>二分法查找
int SearchList_Sq(SqList L,ElemType ELEM)
{
int low,high,mid;
low = 0;
high = L.length - 1;
while(low <= high)
{
mid = (low + high)/2;
if(ELEM < L.elem[mid])
{
high = mid + 1;
}
else if(ELEM > L.elem[mid])
{
low = mid + 1;
}
else
{
return mid+1;
}
}
return -1;
}
///逆转线性表元素
void SWAP(int *m,int *n)
{
int iTemp = *m;
*m = *n;
*n = iTemp;
}
void ReversalList_Sq(SqList &L)
{
int m = 0,n = L.length - 1;
while(m <= n)
{
SWAP(&L.elem[m],&L.elem[n]);
m ++,n --;
}
}
///线性表合并
void MergeList(SqList La,SqList Lb,SqList &Lc)
{
InitList_Sq(Lc);
int i,j;
i = j = 1;
int k = 0;
ElemType ai,bj;
int La_len = La.length,Lb_len = Lb.length;
while((i <= La_len)&&(j <= Lb_len))
{
ai = La.elem[i-1];
bj = Lb.elem[j-1];
if(ai <= bj)
{
ListInsert_Sq(Lc, ++k, ai);
++ i;
}
else
{
ListInsert_Sq(Lc, ++k, bj);
++ j;
}
}
while(i <= La_len)
{
ai = La.elem[i-1];
i ++;
ListInsert_Sq(Lc, ++k, ai);
}
while(j <= Lb_len)
{
bj = La.elem[j-1];
j ++;
ListInsert_Sq(Lc, ++k, bj);
}
}
int main(void)
{
int LENGTH_La,LENGTH_Lb;//线性表La的长度
SqList La,Lb,Lc; //
scanf("%d",&LENGTH_La);
InitList_Sq(La);
Creat_List_Sq(La,LENGTH_La);
printf("创建好的线性表La=");
Output_List_Sq(La);
int index;
ElemType ELEM_1;
scanf("%d%d", &ELEM_1, &index);
ListInsert_Sq( La, index, ELEM_1);
printf("插入一个元素后的线性表La=");
Output_List_Sq(La);
scanf("%d", &index);
ListDelete_Sq( La, index, ELEM_1);
printf("删除一个元素后的线性表La=");
Output_List_Sq(La);
scanf("%d",&ELEM_1);
if(SearchList_Sq(La,ELEM_1) == -1)
{
puts("没找到");
}
else
{
printf("找到，%d在第%d个位置\n",ELEM_1,SearchList_Sq(La,ELEM_1));
}
ReversalList_Sq(La);
printf("逆置后的线性表La=");
Output_List_Sq(La);
scanf("%d",&LENGTH_Lb);
InitList_Sq(Lb);
Creat_List_Sq(Lb,LENGTH_Lb);
MergeList( La, Lb, Lc);
printf("合并La和Lb后的线性表=");
Output_List_Sq(Lc);
return 0;
}
测试数据 为 只是这个测试点过不去
10
29358 26962 26500 24464 19169 18467 15724 11478 6334 41
18818 6
6
26962
7
491 2995 4827 5436 9961 11942 16827
求大鸟帮我改下
[解决办法]
你的链表内部数据不是有序的，为什么要用二分法进行查找呢？？还有就是你的二分法也写错了。
