线性表-1 顺序表 – ShinJiのBlog

一：实现顺序表各种基本运算的算法

//顺序表运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType; 
typedef struct 
{	ElemType data[MaxSize];		//存放顺序表元素
   	int length;					//存放顺序表的长度
} SqList;						//声明顺序表的类型
void CreateList(SqList *&L,ElemType a[],int n) //整体建立顺序表
{
	L=(SqList *)malloc(sizeof(SqList));
	for (int i=0;i<n;i++)
		L->data[i]=a[i];
	L->length=n;
}
void InitList(SqList *&L)	//初始化线性表
{
	L=(SqList *)malloc(sizeof(SqList));	//分配存放线性表的空间
	L->length=0;
}
void DestroyList(SqList *&L)  //销毁线性表
{
	free(L);
}
bool ListEmpty(SqList *L)	//判线性表是否为空表
{
	return(L->length==0);
}
int ListLength(SqList *L)	//求线性表的长度
{
	return(L->length);
}
void DispList(SqList *L)	//输出线性表
{
	for (int i=0;i<L->length;i++)
		printf("%c ",L->data[i]);
	printf("\n");
}
bool GetElem(SqList *L,int i,ElemType &e)	//求线性表中第i个元素值
{
	if (i<1 || i>L->length)
		return false;
	e=L->data[i-1];
	return true;
}
int LocateElem(SqList *L, ElemType e)	//查找第一个值域为e的元素序号
{
	int i=0;
	while (i<L->length && L->data[i]!=e) i++;
	if (i>=L->length)
		return 0;
	else
		return i+1;
}
bool ListInsert(SqList *&L,int i,ElemType e)	//插入第i个元素
{
	int j;
	if (i<1 || i>L->length+1 || L->length==MaxSize)
		return false;
	i--;						//将顺序表位序转化为elem下标
	for (j=L->length;j>i;j--) 	//将data[i]及后面元素后移一个位置
		L->data[j]=L->data[j-1];
	L->data[i]=e;
	L->length++;				//顺序表长度增1
	return true;
}
bool ListDelete(SqList *&L,int i,ElemType &e)	//删除第i个元素
{
	int j;
	if (i<1 || i>L->length)
		return false;
	i--;						//将顺序表位序转化为elem下标
	e=L->data[i];
	for (j=i;j<L->length-1;j++)	//将data[i]之后的元素前移一个位置
		L->data[j]=L->data[j+1];
	L->length--;				//顺序表长度减1
	return true;
}

二：将顺序表按基准划分。

内容：有一顺序表L，假设元素类型是int，顺序表现有9个元素，最大空间maxsize设置为16个元素。现有分别是3，8，2，7，1，5，6，4，8.设计一个尽可能高效的算法，完成以下功能（可以参考，但不调用sqlist.cpp文件）

（1）通过整型数组，建立顺序表L，在控制台显示顺序表L的所有元素

（2）在顺序表第1个位置，插入一个元素4，在控制台显示顺序表L的所有元素

（3）在顺序表最后，插入一个元素0，在控制台显示顺序表L的所有元素

（4）以顺序表的第一个元素4为基准，将所有小于等于它的元素都移到该基准的前面，将所有大于它的元素都移到该基准的后面。

#include<stdio.h>
#include<malloc.h>
#define MaxSize 16
typedef int ElemType;
typedef struct
{
	ElemType data[MaxSize];		
	int length;					
} SqList;
void CreateList(SqList*& L, ElemType a[], int n) 
{
	L = (SqList*)malloc(sizeof(SqList));
	for (int i = 0; i < n; i++)
		L->data[i] = a[i];
	L->length = n;
}
void InitList(SqList*& L)	
{
	L = (SqList*)malloc(sizeof(SqList));	
	L->length = 0;
}
void DispList(SqList* L)	
{
	for (int i = 0; i < L->length; i++)
		printf("%d ", L->data[i]);
	printf("\n");
}
bool ListInsert(SqList*& L, int i, ElemType e)	
{
	int j;
	if (i<1 || i>L->length + 1 || L->length == MaxSize)
		return false;
	i--;						
	for (j = L->length; j > i; j--) 	
		L->data[j] = L->data[j - 1];
	L->data[i] = e;
	L->length++;				
	return true;
}
void TransList(SqList*& L,int n)
{
	n = n - 1;
	int i=0,j=L->length-1,k;
	ElemType base =L->data[n];
	while (i < j)
	{
		while (i<j && L->data[j]>base)
			j--;
		while (i < j && L->data[i] <= base)
			i++;
		if (i < j)
		{
			k = L->data[i];
			L->data[i] = L->data[j];
			L->data[j] = k;
		}
	}
	k = L->data[i];
	L->data[i] = L->data[n];
	L->data[n] = k;

}
int main()
{
	SqList* L;
	int a[MaxSize] = { 3,8,2,7,1,5,6,4,8 };
	InitList(L);
	CreateList(L, a, 9);
	printf("（1）顺序表L所有元素：");
	DispList(L);
	ListInsert(L,1,4);
	printf("（2）第一个位置插入元素4后所有元素：");
	DispList(L);
	ListInsert(L, L->length+1, 0);
	printf("（3）第最后位置插入元素0后所有元素：");
	DispList(L);
	TransList(L,1);
	printf("（4）以第一个数为基准后所有元素：");
	DispList(L);
	return 1;
}

三：LeetCode4—寻找两个正序数组的中位数。

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int n1 = nums1.size();
        const int n2 = nums2.size();
        if(n1>n2) return findMedianSortedArrays(nums2, nums1);
        const int k = (n1 + n2 + 1)/2;
        int left = 0;
        int right = n1;
        while(left < right){
            const int m1 = left + (right - left)/2;
            const int m2 = k - m1;
            if(nums1[m1]<nums2[m2-1])
                left = m1 + 1;
            else
                right = m1;
        }
        const int m1 = left;
        const int m2 = k - left;
        const int c1 = max(m1 <= 0 ? INT_MIN:nums1[m1-1],
                          m2 <= 0 ? INT_MIN:nums2[m2-1]);
        if((n1 + n2)%2 == 1)
            return c1;
        const int c2 = min(m1 >= n1 ? INT_MAX: nums1[m1],
                      m2 >= n2 ? INT_MAX : nums2[m2]);
        return (c1 + c2) * 0.5;
    }
};

四：LeetCode26 —删除排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int fast = 1, slow = 1;
    while (fast < numsSize) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

五：LeetCode27—移除元素。

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

int removeElement(int* nums, int numsSize, int val) {
    int left = 0, right = numsSize;
    while (left < right) {
        if (nums[left] == val) {
            nums[left] = nums[right - 1];
            right--;
        } else {
            left++;
        }
    }
    return left;
}

ps：LeetCode这几题都是复制粘贴的官方标答，目前还不会。

评论

发送评论编辑评论

评论

发送评论 编辑评论

发送评论编辑评论