精华内容
下载资源
问答
  • 将两个顺序存储有序表A和B合成一个有序表C的算法 假设A、B和C的类型下述SqList类型: #define maxlen 1000 typedef int elemtype typedef struct { elemtype elem[maxlen]; int len; }SqList; 设A和B的数据元素...

    将两个顺序存储的有序表A和B合成一个有序表C的算法

    假设A、B和C的类型为下述SqList类型:
    #define maxlen 1000
    typedef int elemtype
    typedef struct
    { elemtype elem[maxlen];
    int len;
    }SqList;

    设A和B的数据元素均为整数且为升序排列,设A的长度为m,B的长度为n,则合并后C的长度为m+n。合并时进行A、B元素的比较,将较小的链入C中,算法描述如下:

    int merge (SqList *A, SqList *B, SqList *C) //将两个有序表A和B合成一个有序表C
    { int m,n,i,j,k;
    m=(*A).len; n=(*B).len;
    if (m+n>maxlen-1)
    { printf(“overflow”);
    exit (0);
    }
    i=0; j=0; //i和j分别作为扫描顺序表A和B的指针
    k=0; //k指示顺序表C中当前位置
    while ((i<=m)&&(j<=n))
    if((*A).elem[i]<=(*B).elem[j])
    { (*C).elem[k]=(*A)elem[i];
    i++; k++;
    }
    else
    { (*C).elem[k]=(*B)elem[j];
    j++; k++;
    }
    while(i<=m) //表B已结束,表A没有结束,链入表A的剩余部分
    { (*C).elem[k]=(*A).elem[i];
    i++; k++;
    }
    while(j<=m) //表A已结束,表B没有结束,链入表B的剩余部分
    { (*C).elem[k]=(*B).elem[j];
    i++; k++;
    }
    return (1);
    }

    展开全文
  • 长度为n顺序表L,编写一个时间复杂度O(n),空间复杂度O(1)的算法 该算法删除线性表中所有值x的数据元素 /*对长度为n顺序表L,编写一个时间复杂度O(n),空间复杂度O(1)的算法 该算法删除...

    题目要求:

    对长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法
    该算法删除线性表中所有值为x的数据元素

    /*对长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法
    该算法删除线性表中所有值为x的数据元素*/
    #include <iostream>
    #include <cstring>
    #include<math.h>
    #define MAXSIZE 20
    #define ElemType int//不加分号
    using namespace std;
    typedef struct {
    	ElemType data[MAXSIZE];
    	int length;
    }SqList;
    bool InitList(SqList &L) {
    	memset(L.data, 0, sizeof(L));
    	if (!L.data)
    		exit(0);
    	L.length = 0;
    	return true;
    }
    void CreateList(SqList &L, int n) {
    	for (int i = 0;i<n;i++) {
    		cin >> L.data[i];
    		L.length++;
    	}
    }
    bool DeleteX(SqList &L,ElemType e) {//推荐做法,更容易想
    	//注释部分的做法没有达到空间复杂度为o(1),也不会满足时间复杂度要求
    	/*int x[MAXSIZE];
    	int j=-1;
    	memset(x, 0, sizeof(x));*/
    	int k=0;//用k来记录所有值不是x的元素的下标,边扫描边统计k,并将不等于x的元素向前移动k个位置,最后修改L的长度
    	for (int i = 0;i <L.length;i++) {
    		if (L.data[i] != e) {
    			/*j++;
    			x[j] = i;*/
    			L.data[k] = L.data[i];
    			k++;
    		}
    		
    	} 
    	L.length = k;
    	return true;
    }
    void DeleteX2(SqList &L, ElemType e) {
    	int k = 0, i = 0;//用k来记录等于x的元素的个数,边扫描L边统计k,并将不等于x的元素前移k个位置,最后修改L的长度
    	while (i<L.length)
    	{
    		if (L.data[i] == e)
    			k++;//用k来记录等于x的元素的个数,边扫描L边统计k
    		else
    			L.data[i - k] = L.data[i];//将不等于x的元素前移k个位置
    		i++;
    	}
    	L.length -= k;//修改L的长度
    }
    void PrintList(SqList L) {
    	cout << "表中元素分别为";
    	for (int i = 0;i<L.length;i++)
    		cout << L.data[i] << "  ";
    	cout << endl;
    }
    int main() {
    	SqList L;
    	InitList(L);
    	int n = 0;
    	cout << "请输入要创建的表的长度:" << endl;
    	cin >> n;
    	cout << "请依次输入各个元素:(用空格隔开)" << endl;
    	CreateList(L, n);
    	cout << "请输入想要删除元素的值(即x的值):" << endl;
    	ElemType e;
    	cin >> e;	
    	DeleteX2(L,e);
    	PrintList(L);
    	return 0;
    }

     

    展开全文
  • 顺序存储(顺序)

    万次阅读 多人点赞 2018-08-25 11:56:23
    把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空间中,既然线性表的每个数据元素的类型相同,所以C语言(其他语言也相同)用一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标0的...

    1.顺序存储方式
      线性表的顺序存储结构,就是在内存中找到一块空间,通过占位的方式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空间中,既然线性表的每个数据元素的类型相同,所以C语言(其他语言也相同)用一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。


    2.顺序存储的属性
    三个属性:

    • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
    • 线性表的最大存储容量:数组的长度MaxSize.
    • 线性表的当前长度:length。

    3.数组长度与线性表长度区别

    类型区别
    数组长度是存放线性表的存储空间长度,存储分配后这个量一般是不变的;但一般用动态分配数组
    线性表长度是线性表中数据元素的个数,随着插入删除操作的进行这个量是变化的

    注:在任意时刻,线性表的长度应该小于等于数组的长度。


    4.地址计算方法
      数学上计数通常从1开始,线性表起始也是1,但C语言数组下标是从0开始的,因此线性表第i个元素对应数组第i-1个元素。这里写图片描述


    5.模块函数

    【1.定义结构体】

    • 定义一个顺序表结构体,里面放置一个数组,一个计算顺序表长度变量,结构体重命名中*pSeqList代表指针类型,方便后面使用。
    #define MAX 10  //数组的大小
    
    typedef int DataType;//将int类型重定义
    
    //定义一个顺序表结构体SeqList
    typedef struct SeqList
    {
        DataType data[MAX];
        int sz;
    }SeqList, *pSeqList;
    

    【2.初始化元素】

    • 将顺序表中的元素初始化为0,顺序表的长度为0.
    void InitSeqList(pSeqList pSeq)
    {
        assert(pSeq);
        pSeq->sz = 0;
    
        //使用memset函数进行初始化
        memset(pSeq->data, 0, sizeof(pSeq->data));
    }

    【3.打印顺序表中的元素】

    • 用for循环进行从头到尾遍历顺序表,将顺序表中的所有元素进行打印。
    void PrintSeqList(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            printf("%d ", pSeq->data[i]);
        }
        printf("\n");
    }

    【4.尾插】

    • 首先判断顺序表满了没有,没满才能继续插入元素。
    • 利用定义计算顺序表长度的变量sz,找到顺序表的最后一个元素将要插入的数据直接赋给最后一个元素几个。
    • 将顺序表长度加1(sz++)。
    void PushBack(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        pSeq->data[pSeq->sz] = d;
        pSeq->sz++;
    }
    

    【5.尾删】

    • 首先对顺序表进行判空处理
    • 在非空的情况下进行顺序表长度减1操作(sz–)
    void PopBack(pSeqList pSeq)
    {
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        pSeq->sz--;
    }
    

    【6.头插】

    • 首先对顺序表进行判空操作
    • 若顺序表非空的情况下,将顺序表中的元素用for循环进行向后移动一位
    • 在要插入的元素赋给数组首元素
    • 顺序表长度加1(sz++)
    void PushFront(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= 0 ; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[0] = d;
        pSeq->sz++;
    }
    

    【7.头删】

    • 对顺序表进行判空
    • 非空将所有元素向前移动一位
    • 顺序表总长度减1(sz- -)
    void PopFront(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }

    【8.查找指定元素】

    • 对顺序表进行判空处理
    • 若非空,利用for循环遍历与所要查找元素比较
    • 找到返回下标,找不到返回 -1
    int Find(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可查!\n");
            return -1;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
            {
                return i;
            }
        }
        return -1;
    }
    

    【9.指定位置插入元素】

    • 对顺序表开辟的空间进行判满处理
    • 将顺序表从后向前向后移动一位,直至到所要插入元素的位置
    • 将所要插入的元素在该指定的位置插入
    • 顺序表总长加1(sz++)
    void Insert(pSeqList pSeq, int pos, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= pos; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[pos] = d;
        pSeq->sz++;
    }
    

    【10.删除指定位置元素】

    • 对顺序表判空处理
    • 从要删除的元素位置起,将往后元素全部向前移动一位
    • 顺序表总长度见1(sz- -)
    void Erase(pSeqList pSeq, int pos)
    {
        int i = 0;
        assert(pSeq && pos >= 0 && pos < pSeq->sz);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = pos; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }

    【11.删除指定元素】

    • 对顺序表进行判空处理
    • 利用for循环遍历判断要删除的元素是否在顺序表中
    • 找到了,就把该元素后面的所有元素向前移动一位
    • 顺序表总长度减1(sz- -)
    void Remove(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
                break;
        }
        if (i == pSeq->sz)
        {
            printf("未找到该元素!\n");
        }
        for (j = i; j < pSeq->sz; j++)
        {
            pSeq->data[j] = pSeq->data[j + 1];
        }
        pSeq->sz--;
    }
    

    【12.删除所有的指定元素 】

    • 对顺序表进行判空处理
    • 利用for循环进行遍历与所要删除的元素比较,若不相同将元素存入新的数组中
    • 删除后顺序表的长度就等于新数组的下标
    void RemoveAll(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] != d)
            {
                pSeq->data[j] = pSeq->data[i];
                j++;
            }
        }
        pSeq->sz = j;
    }
    

    【13.返回顺序表大小】

    • 直接返回顺序表的长度
    int Size(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz;
    }

    【14.对顺序表进行判空】

    • 直接比较顺序表的长度是否为 0
    int Empty(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz == 0;
    }

    【15.冒泡排序】

    • 利用两层for循环使每个元素进行比较让大的元素向后移动
    • 其中flag作为一个标志如果为1表示后面的元素是有序的,减少后面的元素继续排序,提高效率
    void BubbleSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        int flag = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            flag = 0;
            for (j = 0; j < pSeq->sz - i - 1; j++)
            {
                if (pSeq->data[j] > pSeq->data[j + 1])
                {
                    int tmp = pSeq->data[j];
                    pSeq->data[j] = pSeq->data[j + 1];
                    pSeq->data[j + 1] = tmp;
                    flag = 1;
                }
            }
            if (0 == flag)
                return;
        }
    }
    

    【16.选择法排序】

    void SelectSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz-1; i++)
        {
            int tmp = 0;
            for (j = 1; j < pSeq->sz - i; j++)
            {
                if (pSeq->data[tmp] < pSeq->data[j])
                {
                    tmp = j;
                }
            }
            if (tmp != pSeq->sz - 1 - i)
            {
                Swap(pSeq->data + tmp, pSeq->data + pSeq->sz - 1 - i);
            }
        }
    }
    

    【17.选择法排序的优化】

    void SelectSortOP(pSeqList pSeq)
    {
        int i = 0;
        int start = 0;
        int end = pSeq->sz - 1;
        assert(pSeq);
        while (start < end)
        {
            int min = start;
            int max = start;
            for (i = start; i < end; i++)
            {
                if(pSeq->data[max] < pSeq->data[i])
                {
                    max = i;
                }
                if (pSeq->data[min] > pSeq->data[i])
                {
                    min = i;
                }
            }
            if (min != start)
            {
                Swap(pSeq->data + min, pSeq->data + start);
            }
            if (max == start)
            {
                max = min;
            }
            if (max != end)
            {
                Swap(pSeq->data + max, pSeq->data + end);
            }
            start++;
            end--;
        }
    }

    【18.二分查找】

    int BinarySearch(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        int left = 0;
        int right = pSeq->sz - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (pSeq->data[mid] < d)
            {
                left = mid + 1;
            }
            else if (pSeq->data[mid] > d)
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }

    【19.二分查找优化】

    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d)
    {
        assert(pSeq);   
        int mid = left + (right - left) / 2;
        if (left > right)
        {
            return -1;
        }
        if (pSeq->data[mid] < d)
        {
            return BinarySearch_R(pSeq, mid + 1, right, d);
        }
        else if (pSeq->data[mid] > d)
        {
            return BinarySearch_R(pSeq, left, mid-1, d);
        }
        else
        {
            return mid;
        }
    }
    

    6.完整代码

    /*****************************************/
    //Seqlist.h
    #ifndef __SEQLIST__H__
    #define __SEQLIST__H__
    
    #include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    
    #define MAX 10
    typedef int DataType;
    
    typedef struct SeqList
    {
        DataType data[MAX];
        int sz;
    }SeqList, *pSeqList;
    
    
    //初始化 
    void InitSeqList(pSeqList pSeq);
    //打印
    void PrintSeqList(pSeqList pSeq);
    //尾部插入 
    void PushBack(pSeqList pSeq, DataType d);
    //尾部删除 
    void PopBack(pSeqList pSeq);
    //头部插入 
    void PushFront(pSeqList pSeq, DataType d);
    //头部删除 
    void PopFront(pSeqList pSeq);
    //查找指定元素 
    int Find(pSeqList pSeq, DataType d);
    //指定位置插入 
    void Insert(pSeqList pSeq, int pos, DataType d);
    //删除指定位置元素 
    void Erase(pSeqList pSeq, int pos);
    //删除指定元素 
    void Remove(pSeqList pSeq, DataType d);
    //删除所有的指定元素 
    void RemoveAll(pSeqList pSeq, DataType d);
    //返回顺序表的大小 
    int Size(pSeqList pSeq);
    //判断顺序表是否为空 
    int Empty(pSeqList pSeq);
    //冒泡排序 
    void BubbleSort(pSeqList pSeq);
    //选择排序 
    void SelectSort(pSeqList pSeq);
    //选择排序的优化 
    void SelectSortOP(pSeqList pSeq);
    //二分查找 
    int BinarySearch(pSeqList pSeq, DataType d);
    //二分查找递归写法 
    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d);
    
    #endif //__SEQLIST__H__
    
    
    /*****************************************/
    //Seqlist.c
    #include "SeqList.h"
    
    //初始化 
    void InitSeqList(pSeqList pSeq)
    {
        assert(pSeq);
        pSeq->sz = 0;
        memset(pSeq->data, 0, sizeof(pSeq->data));
    }
    
    //打印
    void PrintSeqList(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            printf("%d ", pSeq->data[i]);
        }
        printf("\n");
    }
    
    //尾部插入 
    void PushBack(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        pSeq->data[pSeq->sz] = d;
        pSeq->sz++;
    }
    
    //尾部删除 
    void PopBack(pSeqList pSeq)
    {
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        pSeq->sz--;
    }
    
    //头部插入 
    void PushFront(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= 0 ; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[0] = d;
        pSeq->sz++;
    }
    
    //头部删除 
    void PopFront(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }
    
    //查找指定元素 
    int Find(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可查!\n");
            return -1;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
            {
                return i;
            }
        }
        return -1;
    }
    
    //指定位置插入 
    void Insert(pSeqList pSeq, int pos, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= pos; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[pos] = d;
        pSeq->sz++;
    }
    
    //删除指定位置元素 
    void Erase(pSeqList pSeq, int pos)
    {
        int i = 0;
        assert(pSeq && pos >= 0 && pos < pSeq->sz);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = pos; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }
    
    //删除指定元素 
    void Remove(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
                break;
        }
        if (i == pSeq->sz)
        {
            printf("未找到该元素!\n");
        }
        for (j = i; j < pSeq->sz; j++)
        {
            pSeq->data[j] = pSeq->data[j + 1];
        }
        pSeq->sz--;
    }
    
    //删除所有的指定元素 
    void RemoveAll(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] != d)
            {
                pSeq->data[j] = pSeq->data[i];
                j++;
            }
        }
        pSeq->sz = j;
    }
    
    //返回顺序表的大小 
    int Size(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz;
    }
    
    //判断顺序表是否为空 
    int Empty(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz == 0;
    }
    
    //冒泡排序 
    void BubbleSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        int flag = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            flag = 0;
            for (j = 0; j < pSeq->sz - i - 1; j++)
            {
                if (pSeq->data[j] > pSeq->data[j + 1])
                {
                    int tmp = pSeq->data[j];
                    pSeq->data[j] = pSeq->data[j + 1];
                    pSeq->data[j + 1] = tmp;
                    flag = 1;
                }
            }
            if (0 == flag)
                return;
        }
    }
    
    void Swap(DataType *x, DataType *y)
    {
        DataType tmp = *x;
        *x = *y;
        *y = tmp;
    }
    
    //选择排序 
    void SelectSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz-1; i++)
        {
            int tmp = 0;
            for (j = 1; j < pSeq->sz - i; j++)
            {
                if (pSeq->data[tmp] < pSeq->data[j])
                {
                    tmp = j;
                }
            }
            if (tmp != pSeq->sz - 1 - i)
            {
                Swap(pSeq->data + tmp, pSeq->data + pSeq->sz - 1 - i);
            }
        }
    }
    
    //选择排序的优化 
    void SelectSortOP(pSeqList pSeq)
    {
        int i = 0;
        int start = 0;
        int end = pSeq->sz - 1;
        assert(pSeq);
        while (start < end)
        {
            int min = start;
            int max = start;
            for (i = start; i < end; i++)
            {
                if(pSeq->data[max] < pSeq->data[i])
                {
                    max = i;
                }
                if (pSeq->data[min] > pSeq->data[i])
                {
                    min = i;
                }
            }
            if (min != start)
            {
                Swap(pSeq->data + min, pSeq->data + start);
            }
            if (max == start)
            {
                max = min;
            }
            if (max != end)
            {
                Swap(pSeq->data + max, pSeq->data + end);
            }
            start++;
            end--;
        }
    }
    
    //二分查找
    int BinarySearch(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        int left = 0;
        int right = pSeq->sz - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (pSeq->data[mid] < d)
            {
                left = mid + 1;
            }
            else if (pSeq->data[mid] > d)
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
    
    //二分查找递归写法 
    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d)
    {
        assert(pSeq);   
        int mid = left + (right - left) / 2;
        if (left > right)
        {
            return -1;
        }
        if (pSeq->data[mid] < d)
        {
            return BinarySearch_R(pSeq, mid + 1, right, d);
        }
        else if (pSeq->data[mid] > d)
        {
            return BinarySearch_R(pSeq, left, mid-1, d);
        }
        else
        {
            return mid;
        }
    }
    
    
    /*****************************************/
    //test.c
    
    #include "SeqList.h"
    
    void TestPushBack()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
    }
    
    void TestPushFront()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushFront(&seq, 1);
        PushFront(&seq, 2);
        PushFront(&seq, 3);
        PushFront(&seq, 4);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
    }
    
    void TestFind()
    {
        int temp = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        temp = Find(&seq, 3);
        if (temp == -1)
        {
            printf("未找到!\n");
        }
        else
        {
            printf("找到了,下标为%d\n", temp);
        }
    }
    
    int TestInsert()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        Insert(&seq, 2, 5);
        PrintSeqList(&seq);
    }
    
    void TestErase()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        Erase(&seq, 2);
        PrintSeqList(&seq);
    }
    
    void TestRemove()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        Remove(&seq, 3);
        PrintSeqList(&seq);
    }
    
    TestRemoveAll()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        RemoveAll(&seq, 2);
        PrintSeqList(&seq);
    }
    int TestSize()
    {
        int count = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        count = Size(&seq);
        printf("顺序表的大小=%d\n", count);
    }
    
    void TestEmpty()
    {
        int tmp;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        tmp = Empty(&seq);
        if (tmp == 1)
        {
            printf("顺序表为空!\n");
        }
        else
        {
            printf("顺序表不为空\n");
        }
    }
    
    void TestBubbleSort()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        BubbleSort(&seq);
        PrintSeqList(&seq);
    }
    
    void TestSelectSort()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        SelectSort(&seq);
        PrintSeqList(&seq);
    }
    
    void TestSelectSortOP()
    {
    
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        SelectSortOP(&seq);
        PrintSeqList(&seq);
    }
    
    void TestBinarySearch()
    {
        int tmp = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        tmp = BinarySearch(&seq, 4);
        if (-1 == tmp)
        {
            printf("未找到该元素!\n");
        }
        else
        {
            printf("找到了,下标为: %d\n", tmp);
        }
    }
    
    void TestBinarySearch_R()
    {
        int tmp = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        tmp = BinarySearch_R(&seq, 0, seq.sz-1, 3);
        if (-1 == tmp)
        {
            printf("未找到该元素!\n");
        }
        else
        {
            printf("找到了,下标为: %d\n", tmp);
        }
    }
    int main()
    {
        //TestPushBack();
        //TestPushFront();
        //TestFind();
        //TestInsert();
        //TestErase();
        //TestRemove();
        //TestRemoveAll();
        //TestSize(); 
        //TestEmpty();
        //TestBubbleSort();
        //TestSelectSort();
        //TestSelectSortOP();
        //TestBinarySearch();
        TestBinarySearch_R();
        system("pause");
        return 0;
    }

    展开全文
  • 已知长度为n的线性表A采用顺序存储结构,请写一尽可能高效的算法,删除线性表中所有值item的数据元素 直接上代码 void DeleteItem (Sqlist *L,int item) { int i=0,j=0,count=0; for(i=0;i<L->length;) ...

    已知长度为n的线性表A采用顺序存储结构,请写一尽可能高效的算法,删除线性表中所有值为item的数据元素

    直接上代码

    void DeleteItem (Sqlist *L,int item)
    {
       	int i=0,j=0,count=0;
    	for(i=0;i<L->length;)
        {
            if(L->elem[i] == item)
            {
                i++;//下一个节点下标
                count++;//数据为item的个数
            }
            else
            {
                L->elem[j] = L->elem[i];//j为需要插入元素的下标
                i++;
                j++;
            }
        }
        L->length -= count;//更改表长
    }
    
    
    展开全文
  • 线性表的顺序存储结构称为顺序。 顺序是用一段地址连续的存储单元依次存储线性表的数据元素,因为线性表中每个元素的类型相同,通常用一维数组来实现线性表,也就是把线性表中相邻的元素存在数组中相邻的位置...
  • *题目:已知长度为n的线性表A采用顺序存储结构,请写一个时间复杂度o(n)、空间复杂度o(1)的算法, * 该算法可删除线性表中所有值item的数据元素。 *编译环境:VC 6.0 */ #include &lt;stdio.h&gt; #...
  • 查找8.2 顺序表8.2.1 顺序表的查找基本思想顺序存储结构下的顺序查找算法平均查找长度8.2.2 有序表的折半查找折半查找的算法思想折半查找算法一般代码二叉搜索树 8.2 顺序表 采用顺序存储结构的数据表称为顺序表。...
  • 有序表的索引顺序结构查找次数分析@(算法学习) 为了提高查找效率,对65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,平均需要执行(B)次关键字比较。 A. 10 B. 14 C. 20 D. ...
  • #include <iostream>...#define MAXSIZE 100 //顺序表可能达到的最大长度 typedef int ElemType; //自定义数据元素类型 typedef struct { ElemType *elem; //存储空间的基地址 int length;...
  • 链表存储,顺序存储

    千次阅读 2017-01-05 12:53:59
    已下转自 ...而顺序存储结构的存储空间在逻辑上是连续的,在物理上也是连续的。 2、链式存储存储密度小,但空间利用率较高;顺序存储存储密度大,但空间利用率较低。 3、顺序结构优点是可以随机读取元素
  • 题目:长度为n顺序表L,编写一个时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素。 思想: 记录等于X的值的个数i,遇到不是X的位置就把值放到前面i个位置上 代码展示: #...
  • 查找 根据给定的某个值,在查找中确定一个其关键字(唯一的标识...顺序查找(针对静态查找),也叫线性查找O(n),从头开始遍历,直到最后一个记录。 优化:添加哨兵//有哨兵的顺序查找 int foo(int *a,int n,int
  • int data[N]; int index;//初始值-1,代表里面没有元素,使用时代表下标。 }*List; 第一种方法:顺序双指针法 指针i控制向后遍历,指针j记录需要交换的位置。、 1、进入循环,当遇到item元素时,不做任何...
  • #include <stream> using namespace std; typedef int ElemType;// 自定义了一个数据类型Elemtype,这里定义的Elemtype和int型是一样的 ...typedef struct//typedef是定义类型的意思, ...//存储空间的基地址 ...
  • 顺序表——有序顺序表的插入

    千次阅读 2017-11-10 11:13:16
    本题要求实现递增顺序表有序插入函数。L是一个递增的有序顺序... 比如:原数据有:2 5,要插入一个元素3,那么插入后顺序表为2 3 5。 要考虑扩容的问题。 函数接口定义: Status ListInsert_SortedSq(SqList &L,
  • c++实现顺序类(顺序存储

    千次阅读 2019-01-22 21:01:23
    //将node变量化,以后node如果要替换双链表节点等,只需要修改此处即可 using namespace std; typedef int dataType; //与上同样的道理,如果数据类型有变化,只需要修改此处即可 class node{ public: d...
  • 线性表 线性表是最简单也是最常用的一种数据结构。 逻辑结构 线性表定义:线性表是具有相同特性的数据元素的一个有限序列。...设序列中第i(i表示逻辑序号)个元素ai(1≤i≤n),则线性表的一般表示:  ...
  • 《数据库》顺序有序表的合并

    千次阅读 2016-03-09 12:50:24
    顺序有序表的合并 算法思想: shoux9ian创建一个新表LC,通过比较指针pa和pb所指向的元素值,一次从表LA或表LB中“摘取”较小的元素插入到LC的最后,当其中一个表变为空时,说明此表的元素已经归并完毕,则需要将另...
  • 有序,后 n-k 个元素有序,设计一个算法使得整个顺序表有序,要求算法的空 间复杂度 O(1)。 solution: 由于题目要求空间复杂度O(1),所以不能另外的构建线性表,只能定义中间变量来防止数据的流失。大概...
  • 直接插入排序(顺序存储、链式存储),折半插入排序(顺序存储),希尔排序(顺序存储) 插入排序 直接插入排序 将元素插入L[i]插入到已有序的子序列L[i-1]中。其基本思想是每次将一个待排序的记录按其关键字大小...
  • 将两个递增的有序链表合并一个递增的有序链表。要求结果链表仍使用原来两个链表约存储空间,不另外占用其他的存储空间。中不允许有重复的数据。
  • //将两个有序链表并一个有序链表算法,该程序也可以cFree环境运行。 // c1.h (程序名) #include<string.h> #include<ctype.h> #include<malloc.h> // malloc()等 #include<limits.h> //...
  • 线性表之顺序存储结构和链式存储结构

    万次阅读 多人点赞 2018-09-28 14:17:06
    顺序存储结构和链式存储结构有所不同,具体区别如下所示: 通过上面的对比,可以得出一些经验性的结论: 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜...
  • 1.逻辑结构上呈线性分布的数据元素在实际的物理存储结构中也同样相互之间紧挨着,这种存储结构称为线性表的顺序存储结构。 也就是说,逻辑上具有线性关系的数据按照前后的次序全部存储在一整块连续的内存空间中,...
  • 有序表

    万次阅读 2018-03-03 10:25:05
    一、有序表的定义所谓有序表,是指这样...若以顺序表、单链表存储有序表,会发现基本运算算法中只有ListInsert()算法与前面对应的运算有所差异,其余都是相同的。有序顺序表的ListInsert()算法如下:void ListInsert...
  • /** * @author:(LiberHome) * @date:Created in 2019/2/27 23:34 .../*已知长度为n的线性表采用顺序结构,写一算法删除该线性表中所有值item的元素*/ public class page06 { public static void mai...
  • 直接上代码 #include<stdio.h> #include<stdlib.h> #define LIST_INIT_SIZE...#define LISTINCREMENT 5// 顺序存储空间的分配增量 #define OVERFLOW 0 #define ok 1 typedef struct{ int *element;//...
  • 两个有序顺序表合并

    千次阅读 2016-07-07 11:52:09
    这是在做数据结构考研题目时遇到的题。 ...已知顺序表A和B的元素个数分别m,n。其中顺序表采用动态分配内存空间,其定义如下: typedef struct{ ElemType *elem; //存储空间基址 int length; //当
  • 题目:将两个有序顺序表合并一个新的顺序表,并由函数返回结果顺序表 (非常典型的算法方法) 算法思想: 第一步:按顺序不断取下两个顺序表中表头较小的结点,存到新的顺序表中 第二步:看哪个顺序表有剩余,将...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 94,933
精华内容 37,973
关键字:

对于长度为n的顺序存储的有序表